算法學習入門Day3_lecode_88 合并兩個有序數組，哦 上帝。

很喜歡一段著名的祈禱詞：願上帝賜我一個平靜的心，去接納我所不能改變的事

物；賜我無限勇氣，去改變那有可能改變的東西；并且賜我智慧去辨識這兩者的差

異。

Leetcode原題

88. 合并兩個有序數組

思路

拿到題目以後，我們還是由簡單思路再到精妙的設計思路。 題目的要求是将nums1和nums2兩個數組合并。且我們已經知道了nums1數組中前m個元素為需要合并的元素，後n個元素為0.

方法一 直接合并排序

那麼我們的第一種想法，就是可以從nums1 中下标為m的元素開始，存儲nums2的元素。然後再利用集合本身的排序方法進行排序

public void merge(int[] nums1, int m, int[] nums2, int n) {
       for (int i=0;i<n;i++){
           nums1[m+i]=nums2[i];
       }
        Arrays.sort(nums1);
       // System.out.println(Arrays.toString(nums1));
    }
           

因為是利用了java本身的排序方法，我們看了一下是使用了快排算法

然後送出執行一下，居然才超過24.18%的使用者 。。。

麻了麻了

方法二 雙指針

有沒有其他的好方法呢，這裡我看了一下官網的提示。它說方法1中，并沒有利用兩個數組已經被排序的性質。為了利用這個性質，我們可以使用雙指針方法，将2個數組看做隊列，每次從2個數組頭部取出比較小的數字放在結果中。如下面的動畫所示：

public void merge(int[] nums1, int m, int[] nums2, int n) {
    int len=m+n;
    int tem[]=new int[len];//定義一個臨時數組
    for (int index=0,nums1Index=0,nums2Index=0;index<len;index++){
         if (nums1Index>=m){
             //數組1已經取完，則完全取數組2即可
             tem[index] =nums2[nums2Index++];
         }
         else if (nums2Index>=n){
             //數組2取完，則完全取數組1即可
             tem[index] = nums1[nums1Index++];
         }else if (nums1[nums1Index]< nums2[nums2Index]){
             //數組1中的元素小于數組2中的元素，取數組1中的數即可
             tem[index] = nums1[nums1Index++];
         }else {
             tem[index] =nums2[nums2Index++];
         }
    }


    for (int i = 0; i <len ; i++) {
        nums1[i]= tem[i];
    }
   // System.out.println(Arrays.toString(nums1));
}
           

這個方法的時間複雜度為 O(M+n)。空間複雜度為O(m+n).多了一個中間數組tem。那麼有沒有辦法省去tem.直接在nums1上操作即可。

方法三：逆向雙指針

這種方法采用了逆向思維，通過觀察我們可以發現nums1後半部分都是空的，我們可以直接覆寫。倒着将nums2的元素合并進來不就好了嘛。于是，我們可以使用指針從後向前周遊。每次取兩者之間的較大值放在nums1的最後面

//倒序的方式插入
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int len=m+n;//總元素長度
        for (int index = len-1,nums1Index = m-1,nums2Index =n-1 ;index>=0; index--) {
            if (nums1Index <0){
                //num1數已經取完，則取num2即可
                nums1[index]=nums2[nums2Index--];
            }else if (nums2Index <0){
                //num2取完，則取num1本身即可
                break;
            }else if (nums1[nums1Index]>nums2[nums2Index]){
                nums1[index] =nums1[nums1Index--];
            }else {
                //num2的元素大于等于num1的元素，取num2的值
                nums1[index] =nums2[nums2Index--];
            }
        }
      //  System.out.println(Arrays.toString(nums1));
    }
           

送出測試，超過了100%的使用者，哈哈，妙啊

因為目前個人算法能力有限，有更好的方法的小夥伴可以在評論區留言分享，大家一起共同進步。

有興趣的老爺，還可以關注我的公衆号【一起收破爛】，回複【006】擷取2022最新java面試資料以及履歷模型120套哦~