Merge Sorted Array

描述： 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.

中文：给定两个排好序的integer类型数组，将其合并为一个有序的数组。

注意：假设数组nums1有足够的存储空间(大于等于m+n)用于存储数组nums2中的元素。数组nums1和nums2中的元素个数分别是m,n

分析：

因为为已排序的数组，并且数组1有足够的空间来存储数组1和数组2中的所有元素 也就意味着数组1后面有N个(n大于等于0）个空位置用于存储数组2中的元素，如果从数组起始位置开始比较，则需要重新开辟一个新的数组用于存储合并之后的数组。如果从末尾开始遍历，则不需要，故从后往前进行遍历。

时间复杂度

T(n)=O(n*n）

代码：

C

void merge(int* nums1, int m, int* nums2, int n) {  
    int index = m + n - 1;
    int i = m - 1;
    int j = n - 1;
    while (j >= 0){
        if (i < 0) nums1[index--] = nums2[j--];
        else nums1[index--] = nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
    }
}

// Test case 
int main(int argc, const char * argv[]) {  
    int a[6] = {3,5,6,0,0,0};
    int b[3] = {1,2,4};
    merge(a, 3, b, 3);
    return 0;
}

C++

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

// Test case 
int main(int argc, const char * argv[]) {  
    Solution s;
    vector<int> num1{0, 3, 6, 7, 100, 0, 0, 0, 0, 0};
    vector<int> num2{2, 4, 6, 8, 10};
    s.merge(num1, 5, num2, 5);
    return 0;
}

Swift

class Solution {

   func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
        var i = m-1, j = n-1, k = m+n-1
        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[k] = nums1[i]
                i -= 1
            } else {
                nums1[k] = nums2[j]
                j -= 1
            }
            k -= 1
        }
        while (j >= 0) {
            nums1[k] = nums2[j]
            k -= 1
            j -= 1
        }
    }
}

// Test case
var s = Solution();  
var a:[Int] = [2,0]  
var b:[Int] = [1]  
s.merge(&a, 1, b, 1)  

Java

public class Solution {

    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i=m+n-1, p1=m-1, p2=n-1;
        while(p1>=0 || p2 >=0){
            if(p1<0){
                nums1[i] = nums2[p2];
                p2--;
            }
            else if(p2<0){
                break;
            }
            else{
                if(nums1[p1] > nums2[p2]){
                    nums1[i] = nums1[p1];
                    p1--;
                }
                else{
                    nums1[i] = nums2[p2];
                    p2--;
                }
            }
            i--;
        }
    }
    // Test case
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] a = {2,0};
        int[] b = {1};
        s.merge(a, 1, b, 1);
    }
}

Python

class Solution:  
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: void Do not return anything, modify nums1 in-place instead.
        """
        while m > 0 and n > 0:
            if nums1[m-1] >= nums2[n-1]:
                nums1[m+n-1] = nums1[m-1]
                m -= 1
            else:
                nums1[m+n-1] = nums2[n-1]
                n -= 1
        if n > 0:
            nums1[:n] = nums2[:n]

 #  Test case
 if __name__=='__main__':
    s = Solution()
    a = [1, 3, 5, 7, 9, 0, 0, 0, 0, 0]
    b = [2, 4, 6, 8, 10]
    c = [1, 3, 6, 7, 99]
    d = [2, 0]
    e = [1]
    s.merge(d, 1, e, 1);
    s.merge(d, 5, c, 5);
    s.merge(a, 5, b, 5);
    s.merge1(a, 5, c, 5);
    s.merge2(a, 5, c, 5)

两行代码搞定的（毫无疑问 PY 呀~~~~~）

class Solution:  
   def merge1(self, nums1, m, nums2, n):
        nums1[m:m+n] = nums2[:n]
        nums1.sort()

本题来自leetcode 整理