文章

[LeetCode] 每日一题 350. 两个数组的交集 II

题目链接

https://leetcode.cn/problems/intersection-of-two-arrays-ii

题目描述

给你两个整数数组 nums1nums2 ,请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数,应与元素在两个数组中都出现的次数一致(如果出现次数不一致,则考虑取较小值)。可以不考虑输出结果的顺序。

示例输入

示例 1

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

示例 2

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

提示

  • 1 <= nums1.length, nums2.length <= 1000

  • 0 <= nums1[i], nums2[i] <= 1000

解题思路

本题要求返回两个数组的交集,且结果中的每个元素出现的次数应该与其在两个数组中都出现的次数一致。如果某个元素在两个数组中的出现次数不一致,则取较小值。

这道题的核心思路是使用哈希表统计一个数组中每个元素的出现次数,然后遍历另一个数组,检查当前元素是否在哈希表中出现,并且其出现次数是否大于0。如果满足条件,则将该元素加入结果列表,并将哈希表中该元素的计数减1。

为了优化空间复杂度,我们可以在一开始先比较两个数组的长度,始终将较短的数组作为第一个输入数组,这样我们可以将哈希表的大小从 O(m) 优化到 O(min(m, n)),其中 mn 分别是两个数组的长度。这在部分情况下能降低空间复杂度。

代码实现

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        if (nums2.length < nums1.length) {
            return intersect(nums2, nums1);
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int n1 : nums1) {
            map.put(n1, map.getOrDefault(n1, 0) + 1);
        }
        List<Integer> ansList = new ArrayList<>();
        for (int n2 : nums2) {
            if (map.getOrDefault(n2, 0) > 0) {
                ansList.add(n2);
                map.put(n2, map.get(n2) - 1);
            }
        }
        int[] ans = new int[ansList.size()];
        for (int i = 0; i < ansList.size(); i++) {
            ans[i] = ansList.get(i);
        }
        return ans;
    }
}

复杂度分析

  • 时间复杂度:O(m + n),其中 mn 分别是 nums1nums2 的长度。我们首先遍历 nums1 来填充哈希表,接着遍历 nums2 来检查交集元素。每个元素的查找和更新哈希表的操作都为 O(1),因此总体时间复杂度为 O(m + n)

  • 空间复杂度:O(min(m, n)),我们只需要一个哈希表来存储较小数组的元素及其出现次数,最坏情况下,空间复杂度为 O(min(m, n))

总结

本题通过哈希表统计一个数组的元素出现次数,再遍历另一个数组来获取交集元素,是解决此类交集问题的常见方法。通过比较两个数组的大小,我们能够优化空间复杂度,确保哈希表的大小最小化。这种优化在一些特定情况下能够有效降低空间消耗,提高效率。

希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。

License:  CC BY 4.0