GuilinDev

Lc0088

05 August 2008

88 - Merge Sorted Array

原题概述

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

  • The number of elements initialized in nums1 and nums2 are m and n respectively.
  • You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Example:

1
2
3
4
5

Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

Output: [1,2,2,3,5,6]

题意与分析

两个排序好的数组nums1和nums2，按照顺序全部元素都放到第一个数组当中，保证装得下所以不用担心nums1数组空间的问题。

这道题实际上是归并排序中的“并”的那一部分。大致的思路就是在nums1中最后一个位置开始（通过原先两个数组的参数代表有效长度，相加得来），把大的数填在后面，这样就不会覆盖nums1前面的数字了，注意别越界就行。

Time：O(m + n)；Space：O(1)；

这道题很有可能和Merge Two Sorted Lists一起问。

代码

直观解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0) {
            return;
        }
        int index = m + n - 1;
        int index1 = m - 1;
        int index2 = n - 1;
        
        //直接比较
        while (index1 >= 0 && index2 >= 0) {
            if (nums1[index1] >= nums2[index2]) {
                nums1[index] = nums1[index1];
                index1--;
            } else {
                nums1[index] = nums2[index2];
                index2--;
            }
            index--;
        }
        //如果nums1没有加完，这段可省略
        if (index1 >= 0) {
            while (index1 >= 0) {
                nums1[index] = nums1[index1];
                index--;
                index1--;
            }
        }
        //如果nums2没有加完
        if (index2 >= 0) {
            while (index2 >= 0) {
                nums1[index] = nums2[index2];
                index--;
                index2--;
            }
        }
    }
}

简约解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0) {
            return;
        }
        int index = m + n - 1;
        int index1 = m - 1;
        int index2 = n - 1;
        
        while (index2 >= 0) { //nums2中还有元素
            if (index1 < 0 || nums2[index2] >= nums1[index1]) { //index1 < 0 表示nums1中的元素已经比较完了
                nums1[index] = nums2[index2];
                index2--;
            } else {
                nums1[index] = nums1[index1];
                index1--;
            }
            index--;
        }
    }
}

//这样写可以短一点: nums1[--length] = (m == 0 || nums[m - 1] < nums[n - 1]) ? nums2[--n] : nums1[--m];可读性为0
This site is open source. Improve this page.