350. Intersection of Two Arrays II

Given two arrays, write a function to compute their intersection.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]

Note:

Each element in the result should appear as many times as it shows in both arrays.

The result can be in any order.

Solution:

nums1找到num2中的存在的元素, nums2共同存在的元素删除, nums1不存在元素删除.

class Solution {
 public:
  vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
    if (nums1.size() == 0 || nums2.size() == 0) return {};
    int i = 0;
    while (i < nums1.size()) {
      int exist = 0;
      for (int j = 0; j < nums2.size(); j++) {
        if (nums1[i] == nums2[j]) {
          nums2.erase(nums2.begin() + j);
          exist = 1;
          break;
        }
      }
      if (!exist) {
        nums1.erase(nums1.begin() + i);
      } else {
        i++;
      }
    }
    return nums1;
  }
};

Follow up:

1, What if the given array is already sorted? How would you optimize your algorithm?

// 两个有序数组求交
class Solution {
 public:
  vector<int> intersect(vector<int> &nums1, vector<int> &nums2) {
    sort(nums1.begin(), nums1.end());
    sort(nums2.begin(), nums2.end());
    vector<int> ans_v;
    int i = 0, j = 0;
    while (i < nums1.size() && j < nums2.size()) {
      if (nums1[i] == nums2[j]) {
        ans_v.push_back(nums1[i]); i++; j++;
      } else {
        nums1[i] < nums2[j] ? i++ : j++;
      }
    }
    return ans_v;
  }
};