LeetCode 查找表专题 2：哈希表的使用

例题：LeetCode 第 350 题：Intersection of Two Arrays II

传送门：英文网址：350. Intersection of Two Arrays II ，中文网址：350. 两个数组的交集 II 。

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

示例 1:

输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]

示例 2:

输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]

说明：

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

进阶:

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

对问题的解读：在结果中，相同元素有多少个就应该显示多少个，但不要求结果有序排列。
追问：
1、如果我们给出的数组是已经排好序的数组，你将如何优化你的算法呢？
2、如果 nums1 的长度要小于 nums2 的长度，那种算法更优？
3、如果 nums2 中的元素都在硬盘上，你不能一次性读取 num2 中的元素。

分析：给定两个数组 nums，求出两个数组的交集。对于两个问题，如果数组有序，又如何求解呢。

思路：因为结果要求计算次数，所以须要将数组其中之一（例如nums1）转换为 map，key 是 num，value 是 num 在 nums 中出现的次数（频次）。特别要注意的是，如果检测到 map1 中频次大于等于 1 的时候，把当前遍历的元素放入结果以后，要把这个频次减去 1 。

Java 代码：

class Solution {


    public int[] intersect(int[] nums1, int[] nums2) {


        Map<Integer, Integer> map1 = new HashMap<Integer, Integer>();
        for (int num : nums1) {
            if (map1.containsKey(num)) {
                map1.put(num, map1.get(num) + 1);
            } else {
                map1.put(num, 1);
            }
        }


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

        for (int num : nums2) {

            if (map1.containsKey(num) && map1.get(num) >= 1) {
                resultList.add(num);
                map1.put(num, map1.get(num) - 1);
            }
        }


        int[] result = new int[resultList.size()];

        for (int i = 0; i < resultList.size(); i++) {
            result[i] = resultList.get(i);
        }

        return result;


    }


    public static void main(String[] args) {
        int[] nums1 = new int[]{1, 2, 2, 1};
        int[] nums2 = new int[]{2, 2};
        Solution solution = new Solution();
        int[] result = solution.intersect(nums1, nums2);
        System.out.println(Arrays.toString(result));
    }
}

Python 代码：

class Solution(object):
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        counter = {}
        for num in nums1:
            counter[num] = counter.get(num, 0) + 1

        result = []
        for num in nums2:
            if num in counter and counter[num] > 0:
                result.append(num)
                counter[num] -= 1
        return result

Python 代码2：排序以后，逐个比较。

class Solution(object):
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        nums1.sort()
        nums2.sort()
        p1 = 0
        p2 = 0
        l1 = len(nums1)
        l2 = len(nums2)
        result = []
        while p1 < l1 and p2 < l2:
            if nums1[p1] < nums2[p2]:
                p1 += 1
            elif nums1[p1] > nums2[p2]:
                p2 += 1
            else:
                result.append(nums1[p1])
                p1 += 1
                p2 += 1
        return result

（本节完）