LeetCode 350. 2つの配列の交差II(C++)
タイトル:
2つの配列を指定し、交差を計算する方法を書きます.
例えば、nums 1=[1,2,2,1],nums 2=[2,2]を与える、[2,2]を返す.
注意:
出力結果の各要素の出現回数は、要素が2つの配列に現れる回数と一致する必要があります.出力結果の順序を考慮しなくてもよい.フォロー:
与えられた配列が順番に並んでいたら?アルゴリズムをどのように最適化しますか?nums 1のサイズがnums 2よりずっと小さい場合、どの方法が優れていますか?nums 2の要素がディスクに格納され、メモリが限られている場合、すべての要素を一度にメモリにロードできません.どうすればいいですか?
考え方:
要素の出現回数を考慮する必要があるためmapストレージと検索を採用する.
2つの配列を指定し、交差を計算する方法を書きます.
例えば、nums 1=[1,2,2,1],nums 2=[2,2]を与える、[2,2]を返す.
注意:
出力結果の各要素の出現回数は、要素が2つの配列に現れる回数と一致する必要があります.出力結果の順序を考慮しなくてもよい.フォロー:
与えられた配列が順番に並んでいたら?アルゴリズムをどのように最適化しますか?nums 1のサイズがnums 2よりずっと小さい場合、どの方法が優れていますか?nums 2の要素がディスクに格納され、メモリが限られている場合、すべての要素を一度にメモリにロードできません.どうすればいいですか?
考え方:
要素の出現回数を考慮する必要があるためmapストレージと検索を採用する.
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
map<int,int> nums1Map;
for(int i = 0; i < nums1.size(); i++){
nums1Map[nums1[i]]++;
}
vector<int> resVec;
for(int i = 0; i < nums2.size(); i++){
if(nums1Map[nums2[i]] > 0){
resVec.push_back(nums2[i]);
nums1Map[nums2[i]]--;
}
}
return resVec;
}
};