c++如何解決兩個數(shù)組的交集問題

這篇文章主要為大家展示了“c++如何解決兩個數(shù)組的交集問題”，內(nèi)容簡而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領(lǐng)大家一起研究并學(xué)習(xí)一下“c++如何解決兩個數(shù)組的交集問題”這篇文章吧。

一、題目描述

給定兩個數(shù)組，編寫一個函數(shù)來計算它們的交集。

示例 1：
輸入：nums1 = [1,2,2,1], nums2 = [2,2]輸出：[2,2]示例 2:輸入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]輸出：[4,9]說明：
輸出結(jié)果中每個元素出現(xiàn)的次數(shù)，應(yīng)與元素在兩個數(shù)組中出現(xiàn)次數(shù)的最小值一致。
我們可以不考慮輸出結(jié)果的順序。

二、解題思路

(1) 哈希表查找

解題思路：

• 用哈希表記錄一個數(shù)組中每個元素出現(xiàn)的次數(shù)，myMap{元素：元素出現(xiàn)次數(shù)}

• 遍歷另一個數(shù)組，當(dāng)哈希表中存在當(dāng)前元素時，則對應(yīng)元素的計數(shù)減1，并將該元素存入res中。

C++實現(xiàn)如下：

class Solution {
   
   
   public:vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
   
   
   if(nums1.empty() || nums2.empty()) return{
   
   
   };// 哈希表記錄集合中每個元素出現(xiàn)的次數(shù)unordered_map<int, int> myMap;for( auto &num : nums1 ) myMap[num]++;
        vector<int> res;// 遍歷數(shù)組2for( int i = 0; i < nums2.size(); ++i ){
   
   
   // 判斷數(shù)組2和集合1是否有公共元素if( myMap.count(nums2[i]) ){
   
   
   // 找到后，則對應(yīng)的元素次數(shù)減1if( myMap[nums2[i]] > 0 )res.emplace_back(nums2[i]);// 減少集合1中該數(shù)的次數(shù)myMap[nums2[i]]--;}}return res;}};

運行結(jié)果：

復(fù)雜度分析：

• 時間復(fù)雜度：使用了兩個for()循環(huán)，且是前后關(guān)系，因此整體的時間復(fù)雜度是O(n+m)，其中 m 和 n 分別是兩個數(shù)組的長度

• 空間復(fù)雜度：新定義了一個集合myMap來存儲數(shù)組nums1中的元素，所以空間復(fù)雜度也是O(n)或O(m)

(2) 排序+雙指針

解題思路：

• 首先對兩個數(shù)組進(jìn)行排序，然后使用兩個指針遍歷兩個數(shù)組

• 初始時，兩個指針分別指向兩個數(shù)組的頭部，每次比較兩個指針指向的兩個數(shù)組中的數(shù)字

• 如果兩個數(shù)字不相等，則將指向較小數(shù)字的指針右移一位，如果兩個數(shù)字相等，將該數(shù)字添加到答案，并將兩個指針都右移一位。

• 當(dāng)至少有一個指針超出數(shù)組范圍時，遍歷結(jié)束。

C++實現(xiàn)如下：

class Solution {
   
   
   public:vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
   
   
   //排序sort(nums1.begin(), nums1.end());sort(nums2.begin(), nums2.end());//獲取數(shù)組長度int len1 = nums1.size();int len2 = nums2.size();//初始指針int index1=0, index2=0;vector<int> res;while(index1<len1 && index2<len2){
   
   
   //如果數(shù)組1元素<數(shù)組2，將數(shù)組1的指針向后移動1位if(nums1[index1] < nums2[index2])index1++;//如果數(shù)組2元素<數(shù)組1，將數(shù)組2的指針向后移動1位else if(nums1[index1] > nums2[index2])index2++;//如果元素值大小相同，則雙指針都向后移動一位，且將當(dāng)前值存入reselse{
   
   
   res.push_back(nums1[index1]);index1++;index2++;}}return res;}};

運行結(jié)果：

復(fù)雜度分析：

• 時間復(fù)雜度：O(mlogm+nlogn)，其中 m 和 n 分別是兩個數(shù)組的長度。對兩個數(shù)組進(jìn)行排序的時間復(fù)雜度是 O(mlogm+nlogn)，遍歷兩個數(shù)組的時間復(fù)雜度是 O(m+n)，因此總時間復(fù)雜度是 O(mlogm+nlogn)。

• 空間復(fù)雜度：除了輸出的數(shù)組res，沒有創(chuàng)建額外的中間數(shù)組，空間復(fù)雜度為O(1)

以上是“c++如何解決兩個數(shù)組的交集問題”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對大家有所幫助，如果還想學(xué)習(xí)更多知識，歡迎關(guān)注億速云行業(yè)資訊頻道！