题目描述

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.

解法一

思路

这题和之前的LeetCode 349. Intersection of Two Arrays（两个数组的交集）唯一区别就是，将相同的数组元素当作不同的个体来看，而非合并为同一元素。例如[1, 2, 2, 3]和[2, 2, 2]的交集是[2, 2]。

那么相对于LeetCode 349. Intersection of Two Arrays（两个数组的交集），这题解法上也只需要将之前的Set替换为Map：

  • 遍历第一个数组时，在记录key的同时也记录元素出现次数

  • 遍历第二个数组时，对于每个元素

    • 如果其出现在Map中，则查看Map的value

      • 如果value为0，则代表此元素为第二个数组中多出现的，忽略。
      • 如果value不为0，则代表此元素在第一个数组中也出现了，输出到结果，并将此value减1。
    • 如果其未出现在Map中，则代表此元素未在第一个数组中出现，忽略。

Python

class Solution:
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        nums1_dict = {}
        for num in nums1:
            nums1_dict[num] = nums1_dict.get(num, 0) + 1
        result = []
        for num in nums2:
            if num in nums1_dict and nums1_dict[num] != 0:
                result.append(num)
                nums1_dict[num] -= 1
        return result

Java

public class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Map<Integer, Integer> nums1Map = new HashMap<>();
        for (int num : nums1) {
            nums1Map.put(num, nums1Map.getOrDefault(num, 0) + 1);
        }
        List<Integer> result = new ArrayList<>();
        for (int num : nums2) {
            if (nums1Map.containsKey(num) && nums1Map.get(num) != 0) {
                result.add(num);
                nums1Map.put(num, nums1Map.get(num) - 1);
            }
        }
        int[] resultArray = new int[result.size()];
        int index = 0;
        for (int item : result) {
            resultArray[index++] = item;
        }
        return resultArray;
    }
}

C++

class Solution {
public:
    vector<int> intersect(vector<int> &nums1, vector<int> &nums2) {
        map<int, int> nums1Map;
        for (int num : nums1) {
            nums1Map[num]++;
        }
        vector<int> resultVector;
        for (int num : nums2) {
            if (nums1Map.find(num) != nums1Map.end() && nums1Map[num] != 0) {
                resultVector.push_back(num);
                nums1Map[num]--;
            }
        }
        return resultVector;
    }
};