【Leetcode】350. Intersection of Two Arrays II（求解数组的交集）

朴灿烈づ我的快乐病毒、 2021-12-11 10:47 180阅读 0赞

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.

**Follow up:**

*  What if the given array is already sorted? How would you optimize your algorithm?
 *  What if *nums1*'s size is small compared to *nums2*'s size? Which algorithm is better?
 *  What if elements of *nums2* are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

题目大意：

给出两个数组求解数组的交集。

解题思路：

对两个数组进行由小到大的排序，我们标记两个数组的首位，分别判断当前的状态。

1.如果当前位置相等，idx1++，idx2++，ans.push\_back；

2.如果当前位置idx1数值较大，则idx2++；

3.如果当前位置idx2数值较大，则idx1++；

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