letcode原題
?排序+雙指針
- 如果兩個數組是有序的，則可以使用雙指針的方法得到兩個數組的交集。
- 首先對兩個數組進行排序，然后使用兩個指針遍歷兩個數組。
- 初始時，兩個指針分別指向兩個數組的頭部。每次比較兩個指針指向的兩個數組中的數字，如果兩個數字不相等，則將指向較小數字的指針右移一位，如果兩個數字相等，將該數字添加到答案，并將兩個指針都右移一位。當至少有一個指針超出數組范圍時，遍歷結束。
std::vector<int>intersect(std::vector<int>&num1,std::vector<int>&num2){std::sort(num1.begin(),num1.end());std::sort(num2.begin(),num2.end());int left = 0;int right = 0;std::vector<int>ans;while (left < num1.size() && right < num2.size()){if (num1[left]==num2[right]){ans.push_back(num1[left]);left++;right++;}if (num1[left]<num2[right]){left++;}if (num1[left]>num2[right]){right++;}}return ans;
}哈希表
- 推薦使用哈希表的方式?
vector<int> intersect(vector<int>& nums1, vector<int>& nums2){if (nums2.size()<nums1.size()){return intersect(nums2,nums1);}std::unordered_map<int,int>map{};for (auto temp : nums1) {++map[temp];}std::vector<int>intersection;for (auto temp:nums2) {if (map.find(temp)!=map.end()){intersection.push_back(temp);map[temp]--;if (map[temp]<=0){map.erase(temp);}}}return intersection;
}
