兩個數(shù)組的交集 I

給定兩個數(shù)組 ??nums1??? 和 ??nums2?? ，返回 它們的交集 。輸出結(jié)果中的每個元素一定是 唯一 的。我們可以 不考慮輸出結(jié)果的順序 。

示例 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

解題思路：

如果兩個數(shù)組是有序的，則可以使用雙指針的方法得到兩個數(shù)組的交集。

首先對兩個數(shù)組進(jìn)行排序，然后使用兩個指針遍歷兩個數(shù)組?？梢灶A(yù)見的是加入答案的數(shù)組的元素一定是遞增的，為了保證加入元素的唯一性，我們需要額外記錄變量 pre 表示上一次加入答案數(shù)組的元素。

初始時，兩個指針分別指向兩個數(shù)組的頭部。每次比較兩個指針指向的兩個數(shù)組中的數(shù)字，如果兩個數(shù)字不相等，則將指向較小數(shù)字的指針右移一位，如果兩個數(shù)字相等，且該數(shù)字不等于 pre ，將該數(shù)字添加到答案并更新 pre 變量，同時將兩個指針都右移一位。當(dāng)至少有一個指針超出數(shù)組范圍時，遍歷結(jié)束。

JavaScript 實現(xiàn)：

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;
};

兩個數(shù)組的交集 II

與 I 相通的類似的一道題：

給你兩個整數(shù)數(shù)組 nums1 和 nums2 ，請你以數(shù)組形式返回兩數(shù)組的交集。返回結(jié)果中每個元素出現(xiàn)的次數(shù)，應(yīng)與元素在兩個數(shù)組中都出現(xiàn)的次數(shù)一致（如果出現(xiàn)次數(shù)不一致，則考慮取較小值）。可以不考慮輸出結(jié)果的順序。

示例 1：

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

示例 2:

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

解題思路：

如果兩個數(shù)組是有序的，則可以使用雙指針的方法得到兩個數(shù)組的交集。

首先對兩個數(shù)組進(jìn)行排序，然后使用兩個指針遍歷兩個數(shù)組。

初始時，兩個指針分別指向兩個數(shù)組的頭部。每次比較兩個指針指向的兩個數(shù)組中的數(shù)字，如果兩個數(shù)字不相等，則將指向較小數(shù)字的指針右移一位，如果兩個數(shù)字相等，將該數(shù)字添加到答案，并將兩個指針都右移一位。當(dāng)至少有一個指針超出數(shù)組范圍時，遍歷結(jié)束。

JavaScript 實現(xiàn)：

/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
var intersect = function(nums1, nums2) {
//將兩個數(shù)組從小到大排序
nums1.sort((a,b) => a-b)
nums2.sort((a,b) => a-b)
let res = []
let key1 = 0, key2 = 0, index = 0
//在兩個指針不達(dá)邊界的前提下不斷推進(jìn)
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
};

到此這篇關(guān)于JavaScript實現(xiàn)兩個數(shù)組的交集 的文章就介紹到這了,更多相關(guān)JS數(shù)組交集 內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論