JavaScript实现两个数组的交集

目录
  • 两个数组的交集 I
  • 两个数组的交集 II

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

相关推荐

  • JS数组交集、并集、差集的示例代码

    本文介绍了JS数组交集.并集.差集,分享给大家,具体如下: 由于下面会用到ES5的方法,低版本会存在兼容,先应添加对应的polyfill Array.prototype.indexOf = Array.prototype.indexOf || function (searchElement, fromIndex) { var index = -1; fromIndex = fromIndex * 1 || 0; for (var k = 0, length = this.length; k <

  • JavaScript获取两个数组交集的方法

    本文实例讲述了JavaScript获取两个数组交集的方法.分享给大家供大家参考.具体如下: 这里传入的数组必须是已经排过序的 /* finds the intersection of * two arrays in a simple fashion. * * PARAMS * a - first array, must already be sorted * b - second array, must already be sorted * * NOTES * * Should have O(

  • JS计算两个数组的交集、差集、并集、补集（多种实现方式）

    方法一:最普遍的做法 使用 ES5 语法来实现虽然会麻烦些,但兼容性最好,不用考虑浏览器 JavaScript 版本.也不用引入其他第三方库. 1,直接使用 filter.concat 来计算 var a = [1,2,3,4,5] var b = [2,4,6,8,10] //交集 var c = a.filter(function(v){ return b.indexOf(v) > -1 }) //差集 var d = a.filter(function(v){ return b.index

  • JavaScript获取多个数组的交集简单实例

    在项目中需要取得多个数组的交集,故本例只是适用于特定场景.比如A数组 var a = {1000,10001,10002,10003}; B数组 var b = {10002, 10003}; C数组var c = {10003}; 需要取得这三个数组的交集数组.      具体思路为:先初始一个最小数组为A数组,元素个数最小的也是数组A的长度.然后再迭代各个数组,取得这几个数组长度最短的为最小长度,同时得到长度最短数组.然后,迭代最小数组与各个数组,开始比较元素相等,使用计数器来判断是否该元素

  • js取两个数组的交集|差集|并集|补集|去重示例代码

    复制代码 代码如下: /** * each是一个集合迭代函数,它接受一个函数作为参数和一组可选的参数 * 这个迭代函数依次将集合的每一个元素和可选参数用函数进行计算,并将计算得的结果集返回 {%example <script> var a = [1,2,3,4].each(function(x){return x > 2 ? x : null}); var b = [1,2,3,4].each(function(x){return x < 0 ? x : null}); alert

  • JavaScript实现两个数组的交集

    目录 两个数组的交集 I 两个数组的交集 II 两个数组的交集 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,

  • JavaScript比较两个数组的内容是否相同(推荐)

    今天意外地发现JavaScript是不能用==或===操作符直接比较两个数组是否相等的. alert([]==[]); // false alert([]===[]); // false 以上两句代码都会弹出false. 因为JavaScript里面Array是对象,==或===操作符只能比较两个对象是否是同一个实例,也就是是否是同一个对象引用.目前JavaScript没有内置的操作符判断对象的内容是否相同. 但是惯性思维让人以为数组也是值,是可以比较的. 如果要比较数组是否相等,就只能遍历数组

  • JavaScript合并两个数组并去除重复项的方法

    本文实例讲述了JavaScript合并两个数组并去除重复项的方法.分享给大家供大家参考.具体实现方法如下: Array.prototype.unique = function() { var a = this.concat(); for(var i=0; i for(var j=i+1; j if(a[i] === a[j]) a.splice(j, 1); } } return a; }; //Demo var array1 = ["a","b"]; var ar

  • Python3实现计算两个数组的交集算法示例

    本文实例讲述了Python3实现计算两个数组的交集算法.分享给大家供大家参考,具体如下: 问题: 给定两个数组,写一个方法来计算它们的交集. 方案一:利用collections.Counter的&运算,一步到位,找到 最小次数 的相同元素. # -*- coding:utf-8 -*- #! python3 def intersect(nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :r

  • LeetCode 刷题 Swift 两个数组的交集

    LeetCode 刷题 Swift 两个数组的交集

    目录 题目 方法一:两个集合 思路及解法 代码 复杂度分析 方法二:排序 + 双指针 思路及解法 代码 复杂度分析 题目 给定两个数组 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] 也是可

  • javascript合并两个数组最简单的实现方法

    在开发的过程中,我们很多时候会遇到需要将两个数组合并成一个数组的情况出现. var arr1 = [1, 2, 3]; var arr2 = [4, 5, 6]; // 将arr1和arr2合并成为[1, 2, 3, 4, 5, 6] 这里总结一下在JavaScript中合并两个数组的方法. for循环数组 这个方式是最简单的,也是最容易实现的. var arr3 = []; // 遍历arr1 for (var i = 0; i < arr1.length; i++) { arr3.push(

随机推荐