Intersection of Two Arrays I & II

349. Intersection of Two Arrays

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]

My Solutions:

题目是求两个数组中同时出现的unique数字，最简单的做法是把两个数组中的所有数字比较一遍。Time: O(m*n)。

除此之外：

方法1: 用hashset储存第一个数组中的所有数字，然后遍历第二个数组。hashset保证了数字的唯一性。

Time: O(M + N); Space: O(min(M, N)), HashSet needs extra space

方法2: 将两个数组先排序，然后用两个pointer同时iterate两个数组，把相同的数字存入一个hashset ，最后把hashset里的数字存入返回值。

Time: O(M*logM + N*logN); Space: extra space needed for sorting

// 方法1
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        HashSet<Integer> set1 = new HashSet<>();
        for (int n : nums1) set1.add(n);
        
        HashSet<Integer> resSet = new HashSet<>();
        for (int n : nums2) {
            if (set1.contains(n)) resSet.add(n);
        }
        
        int[] res = new int[resSet.size()];
        int index = 0;
        for (int n : resSet) res[index++] = n;
        return res;
    }
}

// 方法2
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        
        Set<Integer> set = new HashSet<>();
        int i = 0, j = 0;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) i++;
            else if (nums1[i] > nums2[j]) j++;
            else {
                set.add(nums1[i]);
                i++;
                j++;
            }
        }
        int[] res = new int[set.size()];
        int k = 0;
        for (Integer n : set) {
            res[k++] = n;
        }
        return res;
    }
}

350. Intersection of Two Arrays II

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

My Solutions：

方法1: 和349相似，但不用hashset，用hashmap储存数字和出现的频率。

Time: O(M + N); Space: O(min(M, N))

方法2: 将两个数组先排序，然后用两个pointer同时iterate两个数组，把相同的数字存入一个arraylist

，最后把arraylist里的数字存入返回值。

Time: O(M*logM + N*logN); Space: extra space needed for sorting

// 方法1
    public int[] intersect(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i = 0; i < nums1.length; ++i) {
            if (map.containsKey(nums1[i]))
                map.put(nums1[i], map.get(nums1[i]) + 1); 
            else
                map.put(nums1[i], 1);
        }

        List<Integer> results = new ArrayList<Integer>();

        for (int i = 0; i < nums2.length; ++i)
            if (map.containsKey(nums2[i]) &&  map.get(nums2[i]) > 0) {
                results.add(nums2[i]);
                map.put(nums2[i], map.get(nums2[i]) - 1); 
            }

        int result[] = new int[results.size()];
        for(int i = 0; i < results.size(); ++i)
            result[i] = results.get(i);

        return result;
    }
    
// 方法2
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        
        ArrayList<Integer> arr = new ArrayList<>();
        int i = 0, j = 0;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) i++;
            else if (nums1[i] > nums2[j]) j++;
            else {
                arr.add(nums1[i]);
                i++;
                j++;
            }
        }
        int[] res = new int[arr.size()];
        int k = 0;
        while (k < arr.size()) {
            res[k] = arr.get(k);
            k++;
        }
        return res;
    }

Follow up:

• What if the given array is already sorted? How would you optimize your algorithm?

• What if nums1's size is small compared to nums2's size? Which algorithm is better?

• What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

Follow-up questions:

1。 方法2更好，因为可以省去排序时间。

2。 方法1更好，因为只需要空间min(M, N)

3。如果nums1足够小，可以使用方法1，把小的数组加入hashmap。如果两个数组都很大，可以把数组拆到足够小。

• We modify Approach 1 to count only elements which belong to the given numeric sub-range.

• We process each numeric sub-ranges one by one until we process all numeric sub-ranges.

• For example:

  • Input constraint:

    • 1 <= nums1.length, nums2.length <= 10^10.

    • 0 <= nums1[i], nums2[i] < 10^5

    • Our memory can store up to 1000 elements.

  • Then we split the numeric range into numeric sub-ranges [0...999], [1000...1999], ..., [99000...99999], then call Approach 1 to process 100 numeric sub-ranges.