天天看點

LeetCode_排序_簡單_349.兩個數組的交集1.題目2.思路3.代碼實作(java)

目錄

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