13518219792
這篇文章主要為大家展示了“c++如何解決兩個數組的交集問題”，內容簡而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領大家一起研究并學習一下“c++如何解決兩個數組的交集問題”這篇文章吧。
網站建設公司,為您提供網站建設,網站制作,網頁設計及定制網站建設服務,專注于成都定制網頁設計,高端網頁制作,對成都崗亭等多個行業擁有豐富的網站建設經驗的網站建設公司。專業網站設計,網站優化推廣哪家好,專業營銷推廣優化,H5建站,響應式網站。
給定兩個數組，編寫一個函數來計算它們的交集。 示例 1： 輸入：nums1 = [1,2,2,1], nums2 = [2,2]輸出：[2,2]示例 2:輸入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]輸出：[4,9]說明： 輸出結果中每個元素出現的次數，應與元素在兩個數組中出現次數的最小值一致。 我們可以不考慮輸出結果的順序。
解題思路：
用哈希表記錄一個數組中每個元素出現的次數，myMap{元素：元素出現次數}
遍歷另一個數組，當哈希表中存在當前元素時，則對應元素的計數減1，并將該元素存入res中。
C++實現如下：
class Solution {
public:vector intersect(vector& nums1, vector& nums2) {
if(nums1.empty() || nums2.empty()) return{
};// 哈希表記錄集合中每個元素出現的次數unordered_map myMap;for( auto &num : nums1 ) myMap[num]++;
vector res;// 遍歷數組2for( int i = 0; i < nums2.size(); ++i ){
// 判斷數組2和集合1是否有公共元素if( myMap.count(nums2[i]) ){
// 找到后，則對應的元素次數減1if( myMap[nums2[i]] > 0 )res.emplace_back(nums2[i]);// 減少集合1中該數的次數myMap[nums2[i]]--;}}return res;}}; 運行結果：
復雜度分析：
時間復雜度：使用了兩個for()循環，且是前后關系，因此整體的時間復雜度是O(n+m)，其中 m 和 n 分別是兩個數組的長度
空間復雜度：新定義了一個集合myMap來存儲數組nums1中的元素，所以空間復雜度也是O(n)或O(m)
解題思路：
首先對兩個數組進行排序，然后使用兩個指針遍歷兩個數組
初始時，兩個指針分別指向兩個數組的頭部，每次比較兩個指針指向的兩個數組中的數字
如果兩個數字不相等，則將指向較小數字的指針右移一位，如果兩個數字相等，將該數字添加到答案，并將兩個指針都右移一位。
當至少有一個指針超出數組范圍時，遍歷結束。
C++實現如下：
class Solution {
public:vector intersect(vector& nums1, vector& nums2) {
//排序sort(nums1.begin(), nums1.end());sort(nums2.begin(), nums2.end());//獲取數組長度int len1 = nums1.size();int len2 = nums2.size();//初始指針int index1=0, index2=0;vector res;while(index1 nums2[index2])index2++;//如果元素值大小相同，則雙指針都向后移動一位，且將當前值存入reselse{
res.push_back(nums1[index1]);index1++;index2++;}}return res;}}; 運行結果：
復雜度分析：
時間復雜度：O(mlogm+nlogn)，其中 m 和 n 分別是兩個數組的長度。對兩個數組進行排序的時間復雜度是 O(mlogm+nlogn)，遍歷兩個數組的時間復雜度是 O(m+n)，因此總時間復雜度是 O(mlogm+nlogn)。
空間復雜度：除了輸出的數組res，沒有創建額外的中間數組，空間復雜度為O(1)
以上是“c++如何解決兩個數組的交集問題”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注創新互聯行業資訊頻道！
