Leetcode

Leetcode.350.Intersection of Two

2019-12-31  本文已影响0人  Jimmy木

题目

给定两个数组,求数组的交集。

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

思路

先排序,对小的数组下手,通过双指针进行比较。

vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
    sort(nums1.begin(),nums1.end());
    sort(nums2.begin(),nums2.end());
    vector<int> big = nums1;
    vector<int> small = nums2;
    if (nums2.size() > nums1.size()) {
        big = nums2;
        small = nums1;
    }

    vector<int> res;
    int j = 0;
    for (int i = 0;i < small.size();i++) {
        cout << "i: " << i << " j: " << j<<endl;
        while (j < big.size() && big[j] < small[i]) j++;
        if (j < big.size() && big[j] == small[i]) {
            res.push_back(small[i]);
            j++;
        }
        if (j >= big.size()) {
            break;
        }
    }
    return res;
}

总结

注意边界条件,双指针的同步性。

上一篇下一篇

猜你喜欢

热点阅读