C/C++---------------LeetCode第350. 两个数组的交集 II

本文主要是介绍C/C++---------------LeetCode第350. 两个数组的交集 II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

两个数组的交集||

题目及要求
双指针
哈希表
在main内使用

题目及要求

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]
示例 2:

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

提示：

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

进阶：

如果给定的数组已经排好序呢？你将如何优化你的算法？
如果 nums1 的大小比 nums2 小，哪种方法更优？
如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

双指针

思路：先排好序，定义两个指针分别指向nums1和nums2，然后哪个指针指向的值小的话就移动那个指针，例如排好序的数组为nums1=1,5,8 nums2=3,5,9，指针分别指向第一个元素，1和5，nums1指向的1小于nums2指向的3，移动nums1的指针到下一个，这个时候nums1指向5，nums2还是指向1，这个时候nums2比较小，这个时候移动nums2的指针，这个时候nums1和nums2都指向了5构成了交集，存入数组，当指针超出数组时退出循环返回存放交集的数组即可

class Solution {
public:vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {sort(nums1.begin(),nums1.end());   //排序sort(nums2.begin(),nums2.end());int len1=nums1.size(),len2=nums2.size();vector<int>intersection;  //存放交集int index1=0,index2=0;while(index1<len1&&index2<len2){   //超出大小的时候退出循环if(nums1[index1]<nums2[index2]){   //nums1小于nums2的话将指向nums1的指针右移一位index1++;}else if(nums1[index1]>nums2[index2]){index2++;}else{intersection.push_back(nums1[index1]);   //如果相等的话就代表是交集的数，存入intersectionindex1++;index2++;}}return intersection;}
};

哈希表

思路：将nums1的元素存入哈希表计数，遍历nums2检查nums2中的元素在cnts数组中的计数是否大于0，如果有出现的话就将这个元素添加到ans数组，然后cnts内的计数减去1,

class Solution {
public:vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {int cnts[1001] = {};   // 根据题目提示初始化数组vector<int> ans;       // 存储最终结果的动态数组for (int &tmp: nums1) {  // 使用范围for循环遍历nums1cnts[tmp]++;         // 对nums1中的每个元素进行计数}for (int &tmp: nums2) {if (cnts[tmp] > 0) { // 首先检查nums2中的元素在cnts数组中的计数是否大于0ans.push_back(tmp); // 如果是，则将该元素添加到结果数组ans中cnts[tmp]--;       // 然后将cnts数组中对应的计数减一}}return ans;  // 返回结果数组}
};

在main内使用

nt main() {Solution solution; // 创建Solution对象vector<int> nums1 = {1, 2, 2, 1}; // 定义第一个数组vector<int> nums2 = {2, 2};       // 定义第二个数组vector<int> result = solution.intersect(nums1, nums2); // 调用intersect方法，并接收结果// 打印结果cout << "Intersection: ";for (int num : result) {cout << num << " ";}cout << endl;return 0;
}