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.

 

这道题也很简单，主要思想就是从后往前做，就好了。

 

Java:

public class Solution {    public void merge(int[] nums1, int m, int[] nums2, int n) {        if (m < 0 || n < 0) {            return;        }        int p1 = m - 1;        int p2 = n - 1;        for (int i = m + n - 1; i >= 0; i--) {            if (p1 < 0) {                System.arraycopy(nums2, 0, nums1, 0, p2 + 1);                return;            } else if (p2 < 0) {                System.arraycopy(nums1, 0, nums1, 0, p1 + 1);                return;            }            if (nums1[p1] > nums2[p2]) {                nums1[i] = nums1[p1];                p1--;            } else {                nums1[i] = nums2[p2];                p2--;            }        }    }}

换了种写法：

public class Solution {    public void merge(int[] nums1, int m, int[] nums2, int n) {        if (m < 0 || n < 0) {            return;        }        int p1 = m - 1;        int p2 = n - 1;        int k = m + n - 1;        while (p1 >= 0 && p2 >= 0) {            if (nums1[p1] > nums2[p2]) {                nums1[k--] = nums1[p1--];            } else {                nums1[k--] = nums2[p2--];            }        }        // while (p1 >= 0) {        //     nums1[k--] = nums1[p1--];        // }        while (p2 >= 0) {            nums1[k--] = nums2[p2--];        }    }}

这种做法比较巧妙的就是注释的地方是不需要的。因为如果p2减到小于0了，那么这个过程就停止了，不需要多copy一次。

那把第一种解法改良一下：

public class Solution {    public void merge(int[] nums1, int m, int[] nums2, int n) {        if (m < 0 || n < 0) {            return;        }        int p1 = m - 1;        int p2 = n - 1;        for (int i = m + n - 1; p1 >= 0 && p2 >= 0; i--) {            if (nums1[p1] > nums2[p2]) {                nums1[i] = nums1[p1--];            } else {                nums1[i] = nums2[p2--];            }        }        if (p1 < 0) {            System.arraycopy(nums2, 0, nums1, 0, p2 + 1);            return;        }    }}

 

C++写法：

class Solution {public:    void merge(vector
         
          & nums1, int m, vector
          
           & nums2, int n) {        if (m < 0 || n < 0) {            return;        }        int p1 = m - 1;        int p2 = n - 1;        int k = m + n - 1;        while (p1 >= 0 && p2 >= 0) {            if (nums1[p1] > nums2[p2]) {                nums1[k--] = nums1[p1--];            } else {                nums1[k--] = nums2[p2--];            }        }        while (p2 >= 0) {            nums1[k--] = nums2[p2--];        }    }};
          
         

还有更简洁的写法也是厉害。不过逻辑是一样的，不知道写的这么短到底好不好，会不会减少可读性。。。

class Solution {public:    void merge(vector
         
          & nums1, int m, vector
          
           & nums2, int n) {        if (m < 0 || n < 0) {            return;        }        int p1 = m - 1, p2 = n - 1, k = m + n - 1;        while (p2 >= 0) {            nums1[k--] = p1 >= 0 && nums1[p1] > nums2[p2] ? nums1[p1--] : nums2[p2--];        }    }};