這是悅樂書的第161次更新，第163篇原創(chuàng)

01 看題和準(zhǔn)備

今天介紹的是LeetCode算法題中Easy級(jí)別的第20題（順位題號(hào)是88）。給定兩個(gè)排序的整數(shù)數(shù)組nums1和nums2，將nums2中的元素合并到nums1中，并且作為一個(gè)排序的數(shù)組。在nums1和nums2中初始化的元素個(gè)數(shù)分別為m和n。假設(shè)nums1有足夠的空間（大于或等于m + n）來保存nums2中的其他元素。例如：

輸入：nums1 = [1,2,3,0,0,0]，m = 3，nums2 = [2,5,6]，n = 3
輸出：[1,2,2,3,5,6]

本次解題使用的開發(fā)工具是eclipse，jdk使用的版本是1.8，環(huán)境是win7 64位系統(tǒng)，使用Java語(yǔ)言編寫和測(cè)試。

02 第一種解法

給的條件很清晰，nums1的長(zhǎng)度大于等于m+n的和，nums2的元素是肯定可以全部放進(jìn)nums1的，既如此，那我們是不是可以先把nums2中的元素添加進(jìn)nums1，從下標(biāo)m開始，移入n個(gè)新的元素，然后再對(duì)nums1進(jìn)行排序，最后得到新的nums1數(shù)組。排序算法使用了冒泡排序，當(dāng)然使用其他的排序算法也是可以的。

public void merge(int[] nums1, int m, int[] nums2, int n) {
    for (int i=m, k=0; i<nums1.length && k < n ; i++,k++) {
        nums1[i] = nums2[k];
    }
    for (int j=0; j<nums1.length-1; j++) {
        for (int h=0; h<nums1.length-1-j; h++) {
            if (nums1[h] > nums1[h+1]) {
                int temp = nums1[h+1];
                nums1[h+1] = nums1[h];
                nums1[h] = temp;
            }
        }
    }
}

03 第二種解法

上面的解法的時(shí)間復(fù)雜度是O(n^2)，那能不能再降低點(diǎn)？讓其更快一點(diǎn)？讓我們來借助例子分析下。

nums1 = [1,2,3,0,0,0]，m = 3
nums2 = [2,5,6]，n = 3

既然最后結(jié)果是將新的nums1排序，那么按照升序來排，兩個(gè)數(shù)組中最大的一個(gè)值肯定在第m+n位。

第一步，分別獲取nums1的第3位元素、nums2的第3位元素，比較兩數(shù)大小，數(shù)值大的放在nums1的第6位，此時(shí)nums1變成了[1,2,3,0,0,6]。

第二步，分別獲取nums1的第3位元素、nums2的第2位元素，比較兩數(shù)大小，數(shù)值大的放在nums1的第5位，此時(shí)nums1變成了[1,2,3,0,5,6]。因?yàn)榈谝徊绞菍ums2的元素移到了nums1，所以nums2向前移動(dòng)一位，但是nums1的第3位并沒有完全確定大小，所以保持不動(dòng)。

第三步，分別獲取nums1的第3位元素、nums2的第1位元素，比較兩數(shù)大小，數(shù)值大的放在nums1的第4位，此時(shí)nums1變成了[1,2,3,3,5,6]。

第四步，分別獲取nums1的第2位元素、nums2的第1位元素，比較兩數(shù)大小，數(shù)值大的放在nums1的第3位，此時(shí)nums1變成了[1,2,2,3,5,6]。

依據(jù)上面的步驟，可以很快的寫出代碼，但是有種特殊情況要考慮，當(dāng)nums1的最小值，也就是nums1的第一位元素，它比nums2的最大值都大的時(shí)候，nums2的元素是要全部移到nums1原元素的前面，此時(shí)在循環(huán)完后，就要加多一個(gè)判斷，判斷nums2的元素下標(biāo)是否已經(jīng)移動(dòng)到了第一位。

public void merge2(int[] nums1, int m, int[] nums2, int n) {
    int i = m - 1;
    int j = n - 1;
    while (i >= 0 && j >= 0) {
        if (nums1[i] > nums2[j]) {
            nums1[i + j + 1] = nums1[i];
            i--;
        } else {
            nums1[i + j + 1] = nums2[j];
            j--;
        }
    }
    while (j >= 0) {
        nums1[i + j + 1] = nums2[j];
        j--;
    }
}

04 驗(yàn)證與測(cè)試

為了驗(yàn)證上面兩種解法的正確性和效率，我們使用了一些數(shù)據(jù)來測(cè)試。

public static void main(String[] args) {
    Easy_088_MergeSortedArray instance = new Easy_088_MergeSortedArray();
    int[] nums1 = {1,2,2,3,4,5,0,0,0};
    int m = 6;
    int[] nums2 = {2,5,8};
    int n = 3;

    long start = System.nanoTime();
    instance.merge(nums1, m, nums2, n);
    long end = System.nanoTime();
    System.out.println("merge---輸出："+Arrays.toString(nums1)+" , 用時(shí)："+(end-start)/1000+"微秒");

    int[] nums3 = {1,2,2,3,4,5,0,0,0};
    int m2 = 6;
    int[] nums4 = {2,5,8};
    int n2 = 3;
    long start2 = System.nanoTime();
    instance.merge2(nums3, m2, nums4, n2);
    long end2 = System.nanoTime();
    System.out.println("merge2---輸出："+Arrays.toString(nums1)+" , 用時(shí)："+(end2-start2)/1000+"微秒");
}

測(cè)試結(jié)果如下

merge---輸出：[1, 2, 2, 2, 3, 4, 5, 5, 8] , 用時(shí)：4微秒
merge2---輸出：[1, 2, 2, 2, 3, 4, 5, 5, 8] , 用時(shí)：2微秒

從運(yùn)行時(shí)間來看，解法二是明顯優(yōu)于解法一的，解法二的時(shí)間復(fù)雜度是O(n)。

05 小結(jié)

可能有人會(huì)想到借助Arrays.sort()方法來排序，但是如果是面試的時(shí)候，還是使用解法二好些。

以上就是全部?jī)?nèi)容，如果大家有什么好的解法思路、建議或者其他問題，可以下方留言交流，點(diǎn)贊、留言、轉(zhuǎn)發(fā)就是對(duì)我最大的回報(bào)和支持！