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 - ;
int j = n - ;
int k = m + n - ;
while (i >= && j >= )
{
if (nums1[i] > nums2[j])
{
nums1[k--] = nums1[i--];
}
else
{
nums1[k--] = nums2[j--];
}
}
while (j >= )
{
nums1[k--] = nums2[j--];
}
}
}https://leetcode.com/problems/merge-sorted-array/#/description
补充一个java的实现：
public class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int index1 = m - , index2 = n - ;
int indexMerge = m + n - ;
while (index1 >= || index2 >= ) {
if (index1 < ) {
nums1[indexMerge--] = nums2[index2--];
} else if (index2 < ) {
nums1[indexMerge--] = nums1[index1--];
} else if (nums1[index1] > nums2[index2]) {
nums1[indexMerge--] = nums1[index1--];
} else {
nums1[indexMerge--] = nums2[index2--];
}
}
}
}主要思想是使用双指针。两个数组都从后向前遍历，比较两个数组中的值，大的插入到nums1的末尾。
如果一个数组已经遍历完了，那么就把另一个数组剩余元素按照倒叙，依次插入（更新）nums1。
补充一个python的实现：
class Solution:
def merge(self, nums1: 'List[int]', m: int, nums2: 'List[int]', n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
i,j,k = m-,n-,m+n- while i >= and j >= :
if nums1[i] < nums2[j]:
nums1[k] = nums2[j]
k -=
j -=
elif nums1[i] > nums2[j]:
nums1[k] = nums1[i]
k -=
i -=
else:
nums1[k] = nums1[i]
k -=
i -=
while j >= :
nums1[k] = nums2[j]
k -=
j -=
return nums1