LeetCode 349. Intersection of Two Arrays（两个数组的交集）

题目描述

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

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

Note:

• Each element in the result must be unique.
• The result can be in any order.

解法一

思路

“交集”即同时出现在两个数组中的元素的集合。那么如何来判断“元素同时出现在两个数组中”呢？实际只需要遍历其中一个数组，对其每个元素检查其是否在另一个数组中，为了加快这个“检查”的速度，不妨把另一个数组首先转换为HashMap，这样每次“检查”的时间复杂度就只有O(1)了。

接下来还有一个问题，如果两个数组中含有重复元素的话该如何处理呢？根据此题题意，输出的交集中应该不含有重复元素，那么遍历的过程中，中间结果也用HashMap保存就好了，这样可以剔除重复元素。

Python

class Solution:
    def intersection(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        nums1_set = set(nums1)
        intersect = set()
        for num in nums2:
            if num in nums1_set:
                intersect.add(num)
        return list(intersect)

Java

public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> nums1Set = new HashSet<>();
        for (int num : nums1) {
            nums1Set.add(num);
        }
        Set<Integer> intersect = new HashSet<>();
        for (int num : nums2) {
            if (nums1Set.contains(num)) {
                intersect.add(num);
            }
        }
        int[] intersectArray = new int[intersect.size()];
        int i = 0;
        for (int num : intersect) {
            intersectArray[i++] = num;
        }
        return intersectArray;
    }
}

C++

class Solution {
public:
    vector<int> intersection(vector<int> &nums1, vector<int> &nums2) {
        set<int> nums1Set(nums1.begin(), nums1.end());
        set<int> intersect;
        for (int num : nums2) {
            if (nums1Set.find(num) != nums1Set.end()) {
                intersect.insert(num);
            }
        }
        return vector<int>(intersect.begin(), intersect.end());
    }
};