算法(17)-两个数组的交集

哈希表

 2024/03/11 

题目(easy)

给定两个数组 nums1 和 nums2 ，返回它们的交集。输出结果中的每个元素一定是唯一的。我们可以 不考虑输出结果的顺序 。

思路

主要使用 unordered_set。

输出结果中的每个元素一定是唯一的，也就是说输出的结果的去重的，同时可以不考虑输出结果的顺序。

能使用数组来做哈希的题目，都限制了数值的大小；这道题目没有限制数值的大小，无法用数组。

而且哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。

所以要使用 set。

const intersection = (nums1, nums2) {
    // 根据数组大小交换操作的数组
    if(nums1.length < nums2.length) {
        const _ = nums1;
        nums1 = nums2;
        nums2 = _;
    }
    const nums1Set = new Set(nums1);
    const resSet = new Set();
    for(let i = nums2.length - 1; i >= 0; i--) {
        if (nums1Set.has(nums2[i])) {
            resSet.add(nums2[i]);
        }
    }
    return Array.from(resSet);
}

原文作者：Yizhou Shen

原文链接：http://shenyizhou.github.io/2024/03/11/2024-03-11-%E7%AE%97%E6%B3%95(17)-%E4%B8%A4%E4%B8%AA%E6%95%B0%E7%BB%84%E7%9A%84%E4%BA%A4%E9%9B%86/

发表日期：March 11th 2024, 12:18:17 pm

更新日期：March 17th 2024, 3:26:35 pm

Next Post

算法(18)-快乐数
Previous Post

算法(16)-有效的字母异位词

CATALOG

1. 题目(easy)
2. 思路