JavaScript實現兩個陣列的交集

2022-03-25 19:00:36

兩個陣列的交集 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陣列交集內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！

JavaScript實現兩個陣列的交集

目錄

兩個陣列的交集 I

兩個陣列的交集 II

熱門文章