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;
}
总结
注意边界条件,双指针的同步性。