LeetCode_排序_簡單_349.兩個數組的交集

目錄

• 1.題目
• 2.思路
• 3.代碼實作（java）

1.題目

給定兩個數組，編寫一個函數來計算它們的交集。

示例 1：

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

輸出：[2]

示例 2：

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

輸出：[9,4]

說明：

輸出結果中的每個元素一定是唯一的。

我們可以不考慮輸出結果的順序。

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/intersection-of-two-arrays

2.思路

（1）排序+雙指針

（1.1）建立一個長度為nums1.length+nums2.length的數組res，用來儲存結果，并且對數組nums1和nums2進行排序；

（1.2）定義變量i、j、k，其初始值均為0，其中i和j分别用來周遊數組nums1和nums2，k表示即将添加到數組res的元素下标；

（1.3）同時周遊數組nums1和nums2：

若nums1[i]=nums2[j]，且k=0或nums1[i]!=res[k-1]時，将nums1[i]添加到res中，并且指針i和j同時向後移動一位；

若nums1[i]<nums2[j]，指針i向後移動一位；

若nums1[i]>nums2[j]，指針j向後移動一位；

（1.4）周遊結束後，将數組res中下标為0~k-1的部分傳回即可。

3.代碼實作（java）

//（1）排序+雙指針
public int[] intersection(int[] nums1, int[] nums2) {
    int len1=nums1.length;
    int len2=nums2.length;
    int[] res=new int[len1+len2];
    //對數組nums1和nums2進行排序
    Arrays.sort(nums1);
    Arrays.sort(nums2);
    int i=0,j=0,k=0;
    while(i<len1 && j<len2){
        if(nums1[i]==nums2[j]){
            //保證交集的互異性
            //若k==0，說明res中暫時還未添加添加元素，此時可以直接添加而不會使得元素重複；
            /*由于數組nums1和nums2都是經過排序了的，是以數組res中依次添加的元素肯定都是有序的，當k!=0但nums1[i]!=res[k-1]時，
              這說明目前元素nums1[i]肯定不在res中，是以也可以直接添加；若k!=0但nums1[i]==res[k-1]時，說明數組res中已經添加過了
              nums1[i]，此時不需要再重複添加nums1[i]。
			*/
            if(k==0 || nums1[i]!=res[k-1]){
                res[k++]=nums1[i];
            }
            i++;
            j++;
        }else if(nums1[i]<nums2[j]){
            i++;
        }else{
            j++;
        }
    }
    //Arrays.copyOfRange(T[] ori,int from,int to):将原始數組ori從下标from開始(包括)複制，複制到上标to(不包括)，生成一個新的數組
    return Arrays.copyOfRange(res,0,k);
}