Leetcode-349-两个数组的交集

Leecode-349-两个数组的交集

思路：哈希表

题目表述

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

示例 1：

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

示例 2：

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

方法：两个set

• 将两个数组都转换成集合
• 然后迭代较小的集合，检查其中每个元素是否在较大的集合中

// 将两个数组都转化为集合
// 然后迭代较小的集合
// 检查其中每个元素是否同样存在较大的集合中
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        HashSet<Integer> set1 = new HashSet<>();
        HashSet<Integer> set2 = new HashSet<>();

        // 把nums1数组存到对应的set1中
        for (int num : nums1) {
            set1.add(num);
        }

        // 把nums2数组存到对应的set2中
        for (int num : nums2) {
            set2.add(num);
        }

        // 从较小的set检查和较大数组的交集
        if (set1.size() < set2.size()) {
            return helper(set1,set2);
        }else {
            return helper(set2,set1);
        }
    }

    private int[] helper(HashSet<Integer> set1, HashSet<Integer> set2) {
        // 创建一个和较小set一样的数组记为result
        int[] result = new int[set1.size()];
        // 交集含有的个数
        int idx = 0;

        // 遍历较小Set
        // 查找较大set中是否存在较小set的元素
        for (Integer num : set1) {
            if (set2.contains(num)){
                result[idx] = num;
                idx++; // 这里idx++完之后会比原数组长度多1
            }
        }

        // 返回一个idx长度的交集
        return Arrays.copyOf(result,idx);
    }
}

复杂度分析

• 时间复杂度： O（m + n） 其中 n 和 m 是数组的长度。
  • 将num1 转换成集合要 O(n )的时间
  • 类似地，将 nums2 转换为集合需要 O(m) 的时间
  • 而在平均情况下，集合的 in/contains 操作只需要 O(1) 的时间。

• 空间复杂度：O(m+n)，最坏的情况是数组中的所有元素都不同。

打赏