0. 题目

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note:
The number of elements initialized in nums1 and nums2 are m and n respectively.
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Example:
Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]

1. c++版本

思想：题目给出nums1的长度是m+n, 所以可以先将nums2的元素链接到nums1的末尾，然后再用mergeSort里面的merge去进行merge处理

    void myMerge(vector<int>&nums, int left, int mid, int right){
        vector<int> tmp;
        int i=left, j=mid;
        while (i<mid && j<=right) {
            if (nums[i] < nums[j]) tmp.push_back(nums[i++]);
            else if(nums[i] == nums[j]) {
                tmp.push_back(nums[i++]);
                tmp.push_back(nums[j++]);
            }
            else tmp.push_back(nums[j++]);
        }
        while (i<mid) {tmp.push_back(nums[i++]);}
        while (j<=right) {tmp.push_back(nums[j++]);}
        nums = tmp;
    }
    void myCopy(vector<int>& nums1, int m, vector<int>&nums2, int n) {
        for (int i=0; i<n; ++i)
             nums1[m+i] = nums2[i];
    }
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        myCopy(nums1, m , nums2, n);
        myMerge(nums1, 0, m, m+n-1);
    }

2. python版本

注意python版本不可以像c++版本那样借助一个临时的list，tmp, 这种leetcode是通不过的。

class Solution(object):
    def myCopy(self, nums1, m, nums2, n):
        for i in range(0, n):
            nums1[m+i] = nums2[i]

    def myMerge(self, nums, left, mid, right):
        tmp = []
        i, j = left, mid
        while i<mid and j<=right:
            if nums[i] < nums[j]:
                tmp.append(nums[i])
                i = i + 1
            elif nums[i] == nums[j]:
                tmp.append(nums[i])
                tmp.append(nums[j])
                i = i+1
                j = j+1
            else:
                tmp.append(nums[j])
                j = j+1
        while i < mid:
           tmp.append(nums[i])
           i = i+1
        while j <= right:
           tmp.append(nums[j])
           j = j+1
        return tmp

        
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: None Do not return anything, modify nums1 in-place instead.
        """
        self.myCopy(nums1, m, nums2, n)
        tmp = self.myMerge(nums1, 0, m, m+n-1)
        print "tmp: ", tmp
        nums1 = tmp;