题目描述

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

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

注意：

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

跟进:

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

我的解法——哈希计数（AC）

哈希计数
时间空间复杂度均为O(n)。
Beat92%

class Solution:
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        dic1 = {}
        dic2 = {}
        
        for now in nums1:
            if(now in dic1):
                dic1[now] += 1
            else:
                dic1[now] = 1
        
        for now in nums2:
            if(now in dic2):
                dic2[now] += 1
            else:
                dic2[now] = 1
        res = []
        for now in dic2:
            if(now in dic1):
                res += [now] * min(dic1[now],dic2[now])
        return res

#最优解法——改进哈希计数

哈希计数，只哈希一个数组。
复杂度：O(n)

public class Solution {  
    public int[] intersect(int[] nums1, int[] nums2) {  
        Map<Integer, Integer> map1 = new HashMap<>();  
        for(int num: nums1) {  
            Integer count = map1.get(num);  
            if (count == null) count = 1; else count ++;  
            map1.put(num, count);  
        }  
        List<Integer> list2 = new ArrayList<>();  
        for(int num: nums2) {  
            Integer count = map1.get(num);  
            if (count == null) continue;  
            list2.add(num);  
            count --;  
            if (count == 0) map1.remove(num); else map1.put(num, count);  
        }  
        int[] result = new int[list2.size()];  
        for(int i=0; i<list2.size(); i++) result[i] = list2.get(i);  
        return result;  
    }  
}  

其他解法——排序再查找

首先将两个数组从小到大排序，后分别用两个指针指向两个数组开头比较大小，将小的数组指针后移。直至两指针指向数字相等时考虑将数字放入res中。
复杂度：O(nlogn)

public class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        List<Integer> list = new ArrayList<>();
        int i=0, j=0;
        while (i<nums1.length && j<nums2.length) {
            if (nums1[i] == nums2[j]) { list.add(nums1[i]); i++; j++; }
            else if (nums1[i] < nums2[j]) i++;
            else j++;
        }
        int[] result = new int[list.size()];
        for(int k=0; k<list.size(); k++) result[k] = list.get(k);
        return result;
    }
}

参考答案

https://zhuanlan.zhihu.com/p/32786833
http://bookshadow.com/weblog/2016/05/21/leetcode-intersection-of-two-arrays-ii/