第JavaScript實現(xiàn)兩個數(shù)組的交集目錄兩個數(shù)組的交集I兩個數(shù)組的交集II

兩個數(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=10000=nums1[i],nums2[i]=1000

解題思路：

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

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

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

JavaScript實現(xiàn)：

varintersection=function(nums1,nums2){

nums1.sort((x,y)=x-y);

nums2.sort((x,y)=x-y);

constlength1=nums1.length,length2=nums2.length;

letindex1=0,index2=0;

constintersection=[];

while(index1length1index2length2){

constnum1=nums1[index1],num2=nums2[index2];

if(num1===num2){

//保證加入元素的唯一性

if(!intersection.length||num1!==intersection[intersection.length-1]){

intersection.push(num1);

index1++;

index2++;

}elseif(num1num2){

index1++;

}else{

index2++;

returnintersection;

};

兩個數(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ù)組進行排序，然后使用兩個指針遍歷兩個數(shù)組。

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

JavaScript實現(xiàn)：

/**

*@param{number[]}nums1

*@param{number[]}nums2

*@return{number[]}

varintersect=function(nums1,nums2){

//將兩個數(shù)組從小到大排序

nums1.sort((a,b)=a-b)

nums2.sort((a,b)=a-b)

letres=[]

letkey1=0,key2=0,index=0

//在兩個指針不達邊界的前提下不斷推進

while(key1nums1.lengthkey2nums2.length){

//判斷nums1[key1]與nums2[key2]的大小，分出大于小于等于三種情況

if(nums1[key1]nums2[key2])