MergeSortedArray [source code]

public class MergeSortedArray {
static
/******************************************************************************/
public class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if (n == 0) return; 
        if (m == 0) {
            for (int i = 0; i < n; i++) {
                nums1[i] = nums2[i];
            }
            return;
        }
        int[] res = new int[nums1.length];
        int tail = 0, i = 0, j = 0;
        while (i < m && j < n) {
            int head1 = nums1[i];
            int head2 = nums2[j];
            if (head1 <= head2) {
                i++;
                res[tail++] = head1;
            } else {
                j++;
                res[tail++] = head2;
            }
        }
        if (i == m) {
            for (int k = tail; k < m + n; k++) {
                res[k] = nums2[j++];
            }
        } else {
            for (int k = tail; k < m + n; k++) {
                res[k] = nums1[i++];
            }
        }
        for (int k = 0; k < m + n; k++) {
            nums1[k] = res[k];
        }
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        MergeSortedArray.Solution tester = new MergeSortedArray.Solution();
        int[][] inputs = {
            {1,3,5,7,0,0,0,0,0}, {4}, {2,4,6,8}, {4},
        };
        for (int i = 0; i < inputs.length / 4; i++) {
            int[] nums1 = inputs[4 * i];
            int m = inputs[1 + 4 * i][0];
            int[] nums2 = inputs[2 + 4 * i];
            int n = inputs[3 + 4 * i][0];
            System.out.print(Printer.array (nums1) + " + " + Printer.array (nums2) + " -> ");
            tester.merge(nums1, m, nums2, n);
            System.out.println(Printer.array (nums1));
        }
    }
}

感觉这个题目的考法可能是想要用 shift 做一个 InPlace, 不过这样速度太蠢了;

merge sorted以前也做过了, 后面证明 sentinel 思路其实不是最快的, 最快的其实是premature exit之后整体 append 的思路;

最后nums1 = res一下是不行的; 要记住 JAVA 最后还是pass by value, 也就是说nums1指向的 array 你是没有办法改变的(这个就是 nums1里面存放的一个指针). 你最后能够改变的, 只有num1->array的 attribute, 也就是 entry;

最后的速度是1ms (6%), 一般化;

这个是 submission 最优解: 0(43)

public class Solution {  
    public void merge(int[] nums1, int m, int[] nums2, int n) {  
        int i = m - 1;  
        int j = n - 1;  
        int k = m + n - 1;  

        while (i >= 0 && j >= 0) {  
            if (nums1[i] > nums2[j]) {  
                nums1[k] = nums1[i];  
                k--; i--;  
            } else {  
                nums1[k] = nums2[j];  
                k--; j--;  
            }  
        }  

        while (j >= 0) {  
            nums1[k] = nums2[j];  
            k--; j--;  
        }  
    }  
}

看完这个算法还是感觉我对这个题目并没有理解到位. 他这里有的一个关键点就是, 他这个算法完成的是 InPlace, 不仅如此, 还更加快;
他的核心技巧就是在 nums1上面使用快慢指针(严格来说并不是快慢指针, 或许叫做先后指针更加贴切);
这样的第一个好处就是直接可以在 nums1上面 InPlace 存储结果, 不需要借助于res;
另外一个好处就是当两个 array 当中有一个提前走完之后的处理; 如果 nums1先走完, 那么直接把 nums2剩余的部分塞进去前面就行了; 但是如果 nums2先走完, 那么就什么也不用干了; 可以想一个极端的例子, 比如[1,2,3,...] [4,5,6]. 那么最后 nums1的部分就自然在 nums1自己的最前面部分;

这个真正要证明其实也很简单的, 假如 nums2先走完, 那么比如 nums1里面还剩余 t 个, 这 t 个不需要移动,因为这t 个肯定是m + n里面最小的 t 个; 基本这样就可以证明了;

discussion 最优解也是这个, 而且还有人将两个循环合并到了一起:

class Solution {  
public:  
    void merge(int A[], int m, int B[], int n) {  
        int p = m-1, q = n-1, i = m+n-1;  
        while ( q>=0 ) {  
            if ( p<0 || B[q] >= A[p] )  
                A[i--] = B[q--];  
            else  
                A[i--] = A[p--];   
        }  
    }  
};

这个合并的巧妙之处在于他利用了 edge case的处理: 如果 nums1先跑完, 那么最后 p 肯定是-1, 因为移动nums1[0]的时候 p 会被多--一次, 所以这个就可以用来判断从此以后, 只考虑nums2, 这个跟nums2在比大小当中失败是一个 branch, 所以干脆就跟这个 branch 合并起来;

另外这里还要学习的一个地方是 || 在 header 里面的使用: 如果 p < 0成立, 那么 || 后面的内容我们是不能让它运行的. 这个有点像conditional if premature exit一样, 第一个 if 的失败, 给后面的 if 带来了implicit assumption(like here, q >= 0 and array access is not illegal).

这个是一个更简练的写法:

class Solution {  
public:  
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {  
        int i = m - 1, j = n - 1, tar = m + n - 1;  
        while (j >= 0) {  
            nums1[tar--] = i >= 0 && nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];  
        }  
    }  
};

感觉 discussion 上面的大部分解都想到了从后面开始, 也就是用一个前后指针的思路;

Problem Description

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

Difficulty:Easy
Total Accepted:168.2K
Total Submissions:526.6K
Contributor: LeetCode
Companies
microsoft bloomberg facebook
Related Topics
array two pointers
Similar Questions
Merge Two Sorted Lists