????????給定兩個數組?nums1?和?nums2?，返回?它們的交集?。輸出結果中的每個元素一定是?唯一?的。我們可以?不考慮輸出結果的順序?。

來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/intersection-of-two-arrays
?

說明：?輸出結果中的每個元素一定是唯一的。 我們可以不考慮輸出結果的順序。

思路

????????這道題目，主要要學會使用一種哈希數據結構：unordered_set，這個數據結構可以解決很多類似的問題。

????????注意題目特意說明：輸出結果中的每個元素一定是唯一的，也就是說輸出的結果的去重的， 同時可以不考慮輸出結果的順序

????????這道題用暴力的解法時間復雜度是O(n^2)，那來看看使用哈希法進一步優(yōu)化。

????????但是要注意，使用數組來做哈希的題目，是因為題目都限制了數值的大小。

而這道題目沒有限制數值的大小，就無法使用數組來做哈希表了。

而且如果哈希值比較少、特別分散、跨度非常大，使用數組就造成空間的極大浪費。

此時就要使用另一種結構體了，set ，關于set，C++ 給提供了如下三種可用的數據結構：

• std::set
• std::multiset
• std::unordered_set

std::set和std::multiset底層實現都是紅黑樹，std::unordered_set的底層實現是哈希表， 使用unordered_set 讀寫效率是最高的，并不需要對數據進行排序，而且還不要讓數據重復，所以選擇unordered_set。????????

思路如圖所示：

?當然本題也有數組法，一樣放在下面。

C++代碼如下：文章來源地址http://www.zghlxwxcb.cn/news/detail-407999.html

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        //set法
        
    //    unordered_set<int> result_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());



       //數組法
       unordered_set<int> result_set;
       int hash[1005] = {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());
    }
};

到了這里，關于兩個數組的交集(力扣刷題)的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！