两个数组的交集 i

给定两个数组​​nums1​​​和​​nums2​​，返回它们的交集。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。

示例 1：

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

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

注：

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

解题思路：

如果两个数组是有序的，则可以使用双指针的方法得到两个数组的交集。

首先对两个数组进行排序，然后使用两个指针遍历两个数组。可以预见的是加入答案的数组的元素一定是递增的，为了保证加入元素的唯一性，我们需要额外记录变量 pre 表示上一次加入答案数组的元素。

初始时，两个指针分别指向两个数组的头部。每次比较两个指针指向的两个数组中的数字，如果两个数字不相等，则将指向较小数字的指针右移一位，如果两个数字相等，且该数字不等于 pre ，将该数字添加到答案并更新 pre 变量，同时将两个指针都右移一位。当至少有一个指针超出数组范围时，遍历结束。

javascript 实现：

var intersection = function(nums1, nums2) {
    
nums1.sort((x, y) =>
     x - y);
    
nums2.sort((x, y) =>
     x - y);
    
const length1 = nums1.length, length2 = nums2.length;
    
let index1 = 0, index2 = 0;
    
const intersection = [];
    
while (index1  length1 &
    &
 index2  length2) {
    
const num1 = nums1[index1], num2 = nums2[index2];

if (num1 === num2) {

// 保证加入元素的唯一性
if (!intersection.length || num1 !== intersection[intersection.length - 1]) {
    
intersection.push(num1);

}
    
index1++;
    
index2++;

}
 else if (num1  num2) {
    
index1++;

}
 else {
    
index2++;

}

}
    
return intersection;

}
    ;

两个数组的交集 ii

与 i 相通的类似的一道题：

给你两个整数数组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]

解题思路：

如果两个数组是有序的，则可以使用双指针的方法得到两个数组的交集。

首先对两个数组进行排序，然后使用两个指针遍历两个数组。

初始时，两个指针分别指向两个数组的头部。每次比较两个指针指向的两个数组中的数字，如果两个数字不相等，则将指向较小数字的指针右移一位，如果两个数字相等，将该数字添加到答案，并将两个指针都右移一位。当至少有一个指针超出数组范围时，遍历结束。

javascript 实现：

/**
* @param {
number[]}
 nums1
* @param {
number[]}
 nums2
* @return {
number[]}

*/
var intersect = function(nums1, nums2) {
    
//将两个数组从小到大排序
nums1.sort((a,b) =>
     a-b)
nums2.sort((a,b) =>
     a-b)
let res = []
let key1 = 0, key2 = 0, index = 0
//在两个指针不达边界的前提下不断推进
while(key1  nums1.length &
    &
 key2  nums2.length){
    
//判断nums1[key1]与nums2[key2]的大小，分出大于小于等于三种情况
if(nums1[key1]  nums2[key2]) key1++
else if(nums1[key1] >
 nums2[key2]) key2++
else{

res[index++] = nums1[key1]
key1++
key2++
}

}

return res
}
    ;
    

声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！