# LeetCode Easy 350. Intersection of Two Arrays II

tags: leetcode

問題

• Explore
• Problems

アイデア

2つの配列の共通部分を求めます．

ただし，同じ要素でも複数個あれば複数個を答えの配列に格納します．

解法

この問題は2つの配列に重複した要素を重複した回数を考慮して答えの配列に入れます．

この場合，配列の初めから終わりに向けて見ると上手く行きます．

std::sortを使います．これによって最初の配列から最後の配列までを見ることが出来ます．

計算量

配列の長さをそれぞれN, Mとします．

• 時間計算量
  • ソートを使う際に$O(Max{(N \log N), (M \log M)})$が必要です．
• 空間計算量
  • 高々どちらかの配列の小さい方の要素分です．
  • $O(Min{N, M})$

C++

class Solution {
public:
  vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
    vector<int> res;
    sort(nums1.begin(), nums1.end());
    sort(nums2.begin(), nums2.end());
    
    int i1 = 0, i2 = 0;
    int size1 = nums1.size(), size2 = nums2.size();
    
    while (i1 < size1 && i2 < size2) {
      if (nums1[i1] == nums2[i2]) {
        res.push_back(nums1[i1]);
        i1++;
        i2++;
      } else if (nums1[i1] < nums2[i2]) {
        i1++;
      } else {
        i2++;
      }
    }
    return res;
  }
};