Merge sorted array

Leave a comment

July 2, 2016 by oneOokay

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.


比较容易想到的有这么两条思路:

  1. 把nums2 copy到nums1的m至n+n的位置之后对整个nums1进行排序:
    1. 时间复杂度是O(n) +对整个nums1排序的复杂度:无论用Arrays.sort()还是其他的quicksort之类,复杂度最好能够达到 O((m+n)log(m+n)). 所以就是O(n) + O((m+n)log(m+n)).
  2. 把nums2的元素一个一个加入到nums1中,加入的时候找到正确的插入位置然后shift nums1,再插入。(这个超级低效率。。。)

最优的应该是:时间复杂度是O(m+n)

用two pointers,一个放在nums1的末端,一个放在nums2的末端,对他们同时开始比较,把较大者放到nums1的n+m-1的位置,然后pointers逐渐往前,放的位置也逐渐往前。知道一个pointer走完一个数组。如果走完的是nums2,说明nums2已经完全merge进入nums1了,结束。如果走完的是nums1,那么pointer2继续走完nums2,把它merge入nums1.

这里不用担心overwritten的问题,因为被overwritten的值一定已经被放到了后面的正确的位置上(从m+n-1开始放的)

public void merge(int[] nums1, int m, int[] nums2, int n) {
 int i = m - 1;
 int j = n - 1;
 int pointer = m + n - 1;
 while (i >= 0 && j >= 0){
 if (nums1[i] > nums2[j]){
 nums1[pointer--] = nums1[i --];
 }else {
 nums1[pointer--] = nums2[j --];
 }
 }
 
 if (i < 0){
 while (j >= 0){
 nums1[pointer --] = nums2[j --];
 }
 }
 }
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

%d bloggers like this: