LeetCode 88. 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.

题目标签：Array

题目给了我们两个有序数组，让我们merge sort，而且nums1 有足够的空间让我们存放两个array。既然是要放到nums1里，那么我们如果比较nums1 和nums2 的数字，如果是nums2 的数字小的话，就要把nums2 的数字存放进nums1，我们还要另外存放nums1的数字，这样就需要额外space了。所以，我们可以从nums1的end 开始遍历回start，然后设两个pointers 分别指向两个array的最后一个数字，这样可以比完大小后直接存放进nums1。注意最后还需要检查一下，nums2是否还有剩下的数字，有的话都需要存进nums1。

Java Solution:

Runtime beats 38.77%

完成日期：04/05/2017

关键词：Array

关键点：Merge sort；Two Pointers；从end遍历回start

public class Solution
{
public void merge(int[] nums1, int m, int[] nums2, int n)
{
/* if m = 0, meaning nums1's elements are all done. Need one more while loop after this
to take care of left elements of nums2.
if n = 0, meaning nums2's elements are done, the rest of nums1's elements are in the
right place. No need to take care of them.
*/
while(m > 0 && n >0)
{
if(nums1[m-1] > nums2[n-1]) // if number 1 > number 2
{
// save nums1's element into nums1's last "empty" spot.
nums1[m+n-1] = nums1[m-1];
m--;
}
else // if number 1 <= number 2
{
// save nums2's element into nums1's last "empty" spot
nums1[m+n-1] = nums2[n-1];
n--;
}
} // check if nums2's elements are not finished.
while(n > 0)
{
// save nums2's rest elements into nums1
nums1[m+n-1] = nums2[n-1];
n--;
}
}
}