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--;
        }
    }
}

参考资料：

http://www.cnblogs.com/springfor/p/3872640.html

 

LeetCode 算法题目列表 - LeetCode Algorithms Questions List