IntersectionOfTwoArraysIIOPT [source code]

public class IntersectionOfTwoArraysIIOPT {
    public int[] intersect(int[] nums1, int[] nums2) {
            Arrays.sort(nums1);
            Arrays.sort(nums2);
            int pnt1 = 0;
            int pnt2 = 0;
            ArrayList<Integer> ls = new ArrayList<Integer>();
            while ((pnt1 < nums1.length) && (pnt2 < nums2.length)){
                if (nums1[pnt1] < nums2[pnt2]) pnt1++;
                else if (nums1[pnt1] > nums2[pnt2]) pnt2++;
                else {
                    ls.add(nums1[pnt1]);
                    pnt1++; pnt2++;
                }
            }
            int len = ls.size();
            int[] res = new int[len];
            for (int i = 0; i < len; i++) {
                res[i] = ls.get(i);
            }
            return res;
    }
}

这个是 submission 最优解, 4(83), 速度还是不错的;

仔细看了一下, 这个好像不是 general 的最优解, 而是针对 sorted 的 followup1. sorted就用2pointers, 这里也是体现了, 思路还是很明确的.

注意这里最后list to array的做法, 利用了一个List.get(int)的 API;

这个是 discussion 上面对于 followup3的解释:

If only nums2 cannot fit in memory, put all elements of nums1 into a HashMap, read chunks of array that fit into the memory, and record the intersections.
If both nums1 and nums2 are so huge that neither fit into the memory, sort them individually (external sort), then read 2 elements from each array at a time in memory, record intersections.

不是特别理解, 我自己刚拿到这个的时候, 想法就是很简单, 类似 followup2一样的做法, 直接binary search in the long array. 因为既然 nums2很长, 那么就用 binary search 来降低因为他的长度而造成的时间成本. //不对, 我这个想法有问题, 如果你要用 binary search, 那么 nums2肯定就要先 sort. 所以最后的时间应该是(长度分别是 m 和 n) O(mlgn + nlgn) = (m<<n) = O(nlgn). 这个是比如这个基本的 linear 的解法的;

两种情况下当然得记得每次search hit之后都要 remove 被 hit 的这个 element;

这个是另外一个人给出的答案:
Q. What if the given array is already sorted? How would you optimize your algorithm?

If both arrays are sorted, I would use two pointers to iterate, which somehow resembles the merge process in merge sort.

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

Suppose lengths of two arrays are N and M, the time complexity of my solution is O(N+M) and the space complexity if O(N) considering the hash. So it's better to use the smaller array to construct the counter hash.

Well, as we are calculating the intersection of two arrays, the order of array doesn't matter. We are totally free to swap to arrays.

Q. 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?

Divide and conquer. Repeat the process frequently: Slice nums2 to fit into memory, process (calculate intersections), and write partial results to memory.

Problem Description

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

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

Note:
Each element in the result should appear as many times as it shows in both arrays.
The result can be in any order.
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?
Difficulty:Easy
Category:Algorithms
Acceptance:44.44%
Contributor: LeetCode
Related Topics
binary search hash table two pointers sort
Similar Questions
Intersection of Two Arrays