LeetCode 88. Merge Sorted Array
这道题的解法比较巧妙
最开始的想法是从前往后开始合并数组,不过发现这样需要不断往后移动数组,时间开销比较大
标准题解是从两个数组的最后一个元素开始比较,将大的放在第一个数组后面空闲的位置[为什么?因为合并之后的数组的大小是确定的,并且两个数组已经是排序好的]。
边界条件:在第一个数组中所有元素都放到正确位置之后,第二个数组还有元素没有放置到第一个数组
从末尾开始合并的思路很巧妙,这个和Longest Common Subsequence 那道题一样,都是从尾部开始考虑问题
package array.No88;
class Solution2 {
public void merge(int[] nums1, int m, int[] nums2, int n) {
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--];
}
}