两个数组的交集 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
};

到此这篇关于JavaScript实现两个数组的交集 的文章就介绍到这了,更多相关JS数组交集 内容请搜索阿兔在线工具以前的文章或继续浏览下面的相关文章希望大家以后多多支持阿兔在线工具!

点赞(0)

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部