349.两个数组的交集

题目:349. 两个数组的交集 - 力扣（LeetCode）

思路:如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费，可以选用set，但这题数组长度小于1000，所以也可以用数组，最后结果去重，所以考虑set存储最后结果，且由于std::set和std::multiset底层实现都是红黑树，std::unordered_set的底层实现是哈希表， 使用unordered_set 读写效率是最高的，并不需要对数据进行排序，而且还不要让数据重复，所以选择unordered_set。

哈希表代码:

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    unordered_set<int>result_set;//存放结果，用set可以给结果去重
    unordered_set<int>nums_set(nums1.begin(),nums1.end());//用哈希表存数据
    for(int num : nums2)
    {
        if(nums_set.find(num) !=nums_set.end())
        result_set.insert(num);
    }
    return vector<int>(result_set.begin(),result_set.end());
    }
};

分析:

• 时间复杂度: O(n + m) m 是最后要把 set转成vector
• 空间复杂度: O(n)

法二:由于本题的数据大小较小，推荐用数组实现，比哈希其实更快，先遍历一遍nums1，出现的数就记为1，再对nums2遍历如果已经为1了，就插入result结果中(此时存储仍是用set可以去重)，最后在转化为数组输出。

数组代码:

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    unordered_set<int>result_set;//存放结果，用set可以给结果去重
    int hash[1001] = {0};
    for(int num : nums1)
    {
        hash[num] = 1;
    }
    for(int num : nums2)
    {
        if( hash[num] == 1 )
        result_set.insert(num);
    }
    return vector<int>(result_set.begin(),result_set.end());
    }
};

• 时间复杂度: O(m + n)
• 空间复杂度: O(n)

原文地址：https://blog.csdn.net/zengxuan151168/article/details/142930901

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！