一、合并兩個有序數(shù)組

本題給出了兩個整數(shù)數(shù)組nums1和nums2，這兩個數(shù)組均是非遞減排列，要求我們將這兩個數(shù)組合并成一個非遞減排列的數(shù)組。題目中還要求我們把合并完的數(shù)組存儲在nums1中，并且為了存儲兩個數(shù)組中全部的數(shù)據(jù)，nums1中給出了空余的空間來存放nums2中的數(shù)據(jù)。本題的做法有很多，在此我們主要討論三種解題思路。

1.先合并后排序

我們可以先將nums2中的元素全部拷貝到nums1中的空閑空間中去，然后再將nums1整體排序即可，代碼如下：

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m;
        int j = 0;
        while(i < m + n) {
            nums1[i++] = nums2[j++];
        }
        Arrays.sort(nums1);
    }
}

復(fù)雜度分析

• 時間復(fù)雜度：O((m+n)log(m+n))。 排序序列長度為 m+n，套用快速排序的時間復(fù)雜度即可，平均情況為 O((m+n)log(m+n))。

• 空間復(fù)雜度：O(log?(m+n))。 排序序列長度為 m+n，套用快速排序的空間復(fù)雜度即可，平均情況為 O(log?(m+n))。

2.正序雙指針

我們可以先將nums1中的數(shù)據(jù)拷貝到一個新的數(shù)組nums3中去，以便于我們對nums1本身的操作，因?yàn)榻o出的兩個數(shù)組是非遞減排序的，所以我們只要在遍歷的過程中每次比較nums2和nums3中的元素，將較小的那個元素放入nums1中即可，具體代碼如下：

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] nums3 = new int[m];//創(chuàng)建新數(shù)組來存放nums1中的數(shù)據(jù)
        for(int i = 0; i < m; i++) {
            nums3[i] = nums1[i];
        }
        int i = 0;
        int o1 = 0;
        int o2 = 0;
        while(o1 < m && o2 < n) {
            if(nums3[o1] < nums2[o2]) {//挑選出較小的數(shù)據(jù)放入nums1，然后對應(yīng)的下標(biāo)后移
                nums1[i++] = nums3[o1++];
            } else {
                nums1[i++] = nums2[o2++];
            }
        }
        while(o1 < m) {//將剩余的數(shù)據(jù)全部放入nums1
            nums1[i++] = nums3[o1++];
        }
        while(o2 < n) {
            nums1[i++] = nums2[o2++];
        }
    }
}

復(fù)雜度分析

• 時間復(fù)雜度：O(m+n)。 指針移動單調(diào)遞增，最多移動 m+n 次，因此時間復(fù)雜度為 O(m+n)。
• 空間復(fù)雜度：O(m+n)。需要建立一個新數(shù)組存放nums1的元素。

3.倒序雙指針

此為上一個解法的優(yōu)化解法，因?yàn)閚ums1中的數(shù)據(jù)存放在數(shù)組的前部分中，后面為了給nums2中的數(shù)據(jù)留空間全部都是空的，那我們就可以從后向前遍歷，這樣就不需要創(chuàng)建新的數(shù)組來存放nums1中的數(shù)據(jù)了。只不過是我們需要每次選取nums1和nums2中較大的那個數(shù)據(jù)，然后從后向前的存入nums1，代碼如下：文章來源地址http://www.zghlxwxcb.cn/news/detail-695205.html

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

復(fù)雜度分析

• 時間復(fù)雜度：O(m+n)。 指針移動單調(diào)遞減，最多移動 m+n 次，因此時間復(fù)雜度為 O(m+n)。
• 空間復(fù)雜度：O(1)。

到了這里，關(guān)于算法訓(xùn)練 第一周的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！