[LintCode/LeetCode] Intersection of Two Arrays I &

enda 發布于2019-08-14 14:03 / 3531人閱讀

摘要：先想到的是，其實也可以，只是需要在遍歷的時候，添加到數組中的數要掉，略微麻煩了一點。在里跑的時候，也要快一點。另一種類似做法的就快的多了。如果是找出所有包括重復的截距呢

Problem

Given two arrays, write a function to compute their intersection.

Notice

Each element in the result must be unique.
The result can be in any order.

Example

Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Challenge

Can you implement it in three different algorithms?

Note

先想到的是HashSet()，其實HashMap也可以，只是需要在遍歷nums2的時候，添加到res數組中的數要remove掉，略微麻煩了一點。在LC里跑的時候，HashSet也要快一點。
另一種類似HashMap做法的BitSet()就快的多了。

Solution HashSet

public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set set1 = new HashSet();
        Set set2 = new HashSet();
        List ans = new ArrayList();
        for (int i = 0; i < nums1.length; i++) set1.add(nums1[i]);
        for (int i = 0; i < nums2.length; i++) {
            if (set1.contains(nums2[i])) set2.add(nums2[i]);
        }
        int[] res = new int[set2.size()];
        int index = 0;
        for (Integer i: set2) res[index++] = i;
        return res;
    }
}

BitSet

public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        int[] res = new int[nums1.length];
        if (nums1.length == 0 || nums2.length == 0) return new int[0];
        int index = 0;
        BitSet set = new BitSet();
        for (int i = 0; i < nums1.length; i++) {
            set.set(nums1[i]);
        }
        for (int i = 0; i < nums2.length; i++) {
            if (set.get(nums2[i]) == true) {
                res[index++] = nums2[i];
                set.set(nums2[i], false);
            }
        }
        return Arrays.copyOfRange(res, 0, index);
    }
}

Follow Up

如果是找出所有包括重復的截距呢？-- Intersection of Two Arrays II

public class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        int k = 0, l1 = nums1.length, l2 = nums2.length;
        int[] result = new int[l1];
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int i = 0, j = 0;
        while (i < l1 && j < l2)
            if (nums1[i] < nums2[j]) i++;
            else if (nums1[i] == nums2[j++]) result[k++] = nums1[i++];
        return Arrays.copyOf(result, k);
    }
}

GPU云服務器云服務器 Intersection Arrays is_subclass_of函數 Arrays類

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64776.html

[LintCode/LeetCode] Intersection of Two Linked Lis

Problem Write a program to find the node at which the intersection of two singly linked lists begins. Example The following two linked lists: A: a1 → a2 ↘ ...

OldPanda 2019-08-14 15:19 評論0 收藏0
[LintCode/LeetCode] Median of two Sorted Arrays

摘要：由于要求的時間，所以選擇二分法。思路是找到兩個數組合并起來的第個元素。這樣只需計算兩個數組的中位數是第幾個元素，代入功能函數即可。據此，根據二分法的性質，我們在遞歸時可以將前即個元素排除。 Problem There are two sorted arrays A and B of size m and n respectively. Find the median of the tw...

vvpvvp 2019-08-14 15:41 評論0 收藏0
[LintCode/LeetCode] Scramble String

摘要：首先將兩個字符串化成字符數組，排序后逐位比較，確定它們等長且具有相同數量的相同字符。然后，從第一個字符開始向后遍歷，判斷和中以這個坐標為中點的左右兩個子字符串是否滿足第一步中互為的條件設分為和，分為和。 Problem Given a string s1, we may represent it as a binary tree by partitioning it to two no...

MASAILA 2019-08-14 15:45 評論0 收藏0
[LintCode/LeetCode] Two Strings are Anagrams/Valid

摘要：建立一個長度為的數組，統計所有個字符在出現的次數，然后減去這些字符在中出現的次數。否則，循環結束，說明所有字符在和中出現的次數一致，返回。 Program Write a method anagram(s,t) to decide if two strings are anagrams or not. Example Given s=abcd, t=dcab, return true....

vslam 2019-08-14 15:22 評論0 收藏0
[LeetCode] Intersection of Two Arrays I & II

Intersection of Two Arrays I Problem Given two arrays, write a function to compute their intersection. Example Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2]. Note Each element in the result m...

lucas 2019-08-14 15:45 評論0 收藏0