)
打卡第二十一天
3道简单题+1道中等题
题目:两个数组的交集
给定两个数组nums1和nums2，返回它们的交集.输出结果中的每个元素一定是唯一的。可以不考虑输出结果的顺序。
思路: 排序+双指针
代码:
class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {sort(nums1.begin(), nums1.end());sort(nums2.begin(), nums2.end());//排序两数组int length1 = nums1.size(), length2 = nums2.size();int index1 = 0, index2 = 0;//初始化双指针,分别指向两个数组的起始位置vector<int> answer;//答案数组while (index1 < length1 && index2 < length2) {//双指针遍历int num1 = nums1[index1], num2 = nums2[index2];//当前指针指向元素值if (num1 == num2) {// 保证加入元素的唯一性:如果结果向量为空，或者当前元素不等于结果向量中的最后一个元素if (!answer.size() || num1 != answer.back()) {answer.push_back(num1);}index1++;index2++;} else if (num1 < num2) {index1++;} else {index2++;}}return answer;}
};
变形:两个数组的交集(ll)
给你两个整数数组nums1和nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。
思路:排序+二分查找
代码:
class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {sort(nums1.begin(), nums1.end());sort(nums2.begin(), nums2.end());//排序两数组int length1 = nums1.size(), length2 = nums2.size();int index1 = 0, index2 = 0;//初始化双指针,分别指向两个数组的起始位置vector<int> answer;//答案数组while (index1 < length1 && index2 < length2) {//双指针遍历int num1 = nums1[index1], num2 = nums2[index2];//当前指针指向元素值if (num1 < num2) {//如果nums1的当前元素较小，移动nums1的指针index1++;} else if (num1 > num2) {//如果nums2的当前元素较小，移动nums2的指针index2++;} else {answer.push_back(num1);//将交集元素加入结果index1++;index2++;} }return answer;}
};
耗时≈1.5小时 明天继续