leetcode解题: Merge Sorted Array (88)

发表于 | 分类于

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： O（M + N）， O（1） Space

本题的function的return是void，看来必须是inplace的。 由于两个array都是sorted， 我们可以从大到小的merge，这样我们可以把merge过的数值插入到第一个array的尾部。
用一个指针维护插入的位置，另两个指针从大到小遍历两个array。
C++

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(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        
        int mp = m - 1;
        int np = n - 1;
        int i = nums1.size() - 1;
        while (mp >= 0 && np >= 0) {
            if (nums1[mp] >= nums2[np]) {
                nums1[i--] = nums1[mp--];
            }else {
                nums1[i--] = nums2[np--];
            }
        }
        while (mp >= 0) {
            nums1[i--] = nums1[mp--];
        }
        while (np >= 0) {
            nums1[i--] = nums2[np--];
        }
        
    }
};

Java

1