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都已经sorted了, merge后长度为m+n; 最后一个元素的位置为m+n-1, 我们可以从后往前面来填。

public class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int pm = m - 1;
        int pn = n - 1;
        int newidx = m + n - 1;
        while(pm >=0 && pn >= 0) {
            if (nums1[pm] >= nums2[pn] ) {
                nums1[newidx] = nums1[pm];
                pm--;
            } else {
                nums1[newidx] = nums2[pn];
                pn--;
            }
            newidx--;
        }

        while(pn >=0) {
            nums1[newidx] = nums2[pn];
            pn--;
            newidx--;
        }

    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s