leetcode88

public class Solution {
    public void Merge(int[] nums1, int m, int[] nums2, int n) {
        //for (int i = 0; i < n; i++)
            //{
                //nums1[m++] = nums2[i];
            //}

            //nums1 = nums1.OrderBy(x => x).ToArray();
            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--];
                }
                else
                {
                    nums1[k--] = nums2[j--];
                }
            }
            while (j >= 0)
            {
                nums1[k--] = nums2[j--];
            }
    }
}

https://leetcode.com/problems/merge-sorted-array/#/description

补充一个java的实现：

 1 public class Solution {
 2     public void merge(int[] nums1, int m, int[] nums2, int n) {
 3         int index1 = m - 1, index2 = n - 1;
 4         int indexMerge = m + n - 1;
 5         while (index1 >= 0 || index2 >= 0) {
 6             if (index1 < 0) {
 7                 nums1[indexMerge--] = nums2[index2--];
 8             } else if (index2 < 0) {
 9                 nums1[indexMerge--] = nums1[index1--];
10             } else if (nums1[index1] > nums2[index2]) {
11                 nums1[indexMerge--] = nums1[index1--];
12             } else {
13                 nums1[indexMerge--] = nums2[index2--];
14             }
15         }
16     }
17 }

主要思想是使用双指针。两个数组都从后向前遍历，比较两个数组中的值，大的插入到nums1的末尾。

如果一个数组已经遍历完了，那么就把另一个数组剩余元素按照倒叙，依次插入（更新）nums1。

补充一个python的实现：

 1 class Solution:
 2     def merge(self, nums1: 'List[int]', m: int, nums2: 'List[int]', n: int) -> None:
 3         """
 4         Do not return anything, modify nums1 in-place instead.
 5         """
 6         i,j,k = m-1,n-1,m+n-1
 7         
 8         while i >= 0 and j >= 0:
 9             if nums1[i] < nums2[j]:
10                 nums1[k] = nums2[j]
11                 k -= 1
12                 j -= 1
13             elif nums1[i] > nums2[j]:
14                 nums1[k] = nums1[i]
15                 k -= 1
16                 i -= 1
17             else:
18                 nums1[k] = nums1[i]
19                 k -= 1
20                 i -= 1
21         while j >= 0:
22             nums1[k] = nums2[j]
23             k -= 1
24             j -= 1
25         return nums1