题目

给定两个数组，写一个方法来计算它们的交集。

例如:
给定 nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2, 2].

注意：

输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
我们可以不考虑输出结果的顺序。

跟进:

如果给定的数组已经排好序呢？你将如何优化你的算法？
如果 nums1 的大小比 nums2 小很多，哪种方法更优？
如果nums2的元素存储在磁盘上，内存是有限的，你不能一次加载所有的元素到内存中，你该怎么办？

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?

解题方法

Map映射

使用HashMap，Key用来保存第一个数组中的元素，Value保存元素存在的个数。然后遍历第二个数组，若对应元素在HashMap中的键值大于0，则将该元素保存到结果数组中，HashMap中对应键值减一。这段代码跑了6ms，超过61.49%的java提交。

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        // Method_01
        HashMap<Integer, Integer> numMap = new HashMap<>();// store nums1
        ArrayList<Integer> numList = new ArrayList<>();// store result
        
        // store nums1 into hashMap
        for (int i :
                nums1) {
            numMap.put(i, (numMap.get(i) == null ? 0 : numMap.get(i)) + 1);
        }
        
        // search the intersection
        for (int i :
                nums2) {
            if (numMap.get(i) != null && numMap.get(i) > 0) {
                numMap.put(i, numMap.get(i) - 1);
                numList.add(i);
            }
        }
        
        // arrayList into array
        int[] result = new int[numList.size()];
        int index = 0;
        for (int i :
                numList) {
            result[index++] = i;
        }
        
        return result;
    }
}

先排序

对于题目中给出的问题如果给定的数组已经排好序呢？你将如何优化你的算法？我们先对两个数组进行排序，然后用一个循环遍历两个数组，使用两个指针进行定位，当两个元素相同则放进结果数组，并且两个指针均前进一步，当不同时，则元素较小的指针向前一步，直到遍历完某个数组。这段代码跑了5ms，超过77.02%的java提交。

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        // Method_02
        // sort the two arrays
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        
        int index1 = 0, index2 = 0;// two point
        int[] nums = new int[nums1.length > nums2.length ? nums2.length : nums1.length];// store result
        int index = 0;// store the size of result
        
        // search the intersection
        while (index1 < nums1.length && index2 < nums2.length) {
            if (nums1[index1] == nums2[index2]) {
                nums[index+++] = nums1[index1++];
                index2++;
            } else if (nums1[index1] > nums2[index2]) {
                index2++;
            } else if (nums1[index1] < nums2[index2]) {
                index1++;
            }
        }

        return Arrays.copyOf(nums, index);
    }
}

使用ArrayList

对于只超过77.02%的成绩并不满意，尝试一下继续缩短时间。本来以为使用数组会比用ArrayList快，结果尝试一下发现结果并不是这样，果然实践才是验证真理的唯一方法。将保存结果的数组换成了ArrayList，最后再将ArrayList转换为数组。这段代码跑了4ms，超过了88.27%的java提交。

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        // Method_03
        // sort the two arrays
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int index1 = 0, index2 = 0;
        ArrayList<Integer> numList = new ArrayList<>();// use ArrayList
        
        while (index1 < nums1.length && index2 < nums2.length) {
            int n1 = nums1[index1];
            int n2 = nums2[index2];
            if (n1 == n2) {
                numList.add(nums1[index1++]);
                index2++;
            } else if (n1 > n2) {
                index2++;
            } else if (n1 < n2) {
                index1++;
            }
        }

        // ArrayList into array
        int[] result = new int[numList.size()];
        int index = 0;
        for (int i :
                numList) {
            result[index++] = i;
        }
        
        return result;
    }
}

结语

一点一点地优化，看着自己的代码越来越快还是很有挺有成就感的！Keep coding！