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.

分析

meh

解决方案1（Python）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        nums1Index, nums2Index = m-1, n-1
        tail = m+n-1
        
        while nums1Index >= 0 or nums2Index >= 0:
            if nums1Index == -1:
                nums1[tail] = nums2[nums2Index]
                nums2Index -= 1
            elif nums2Index == -1:
                nums1[tail] = nums1[nums1Index]
                nums1Index -= 1
            elif nums1[nums1Index] > nums2[nums2Index]:
                nums1[tail] = nums1[nums1Index]
                nums1Index -= 1
            else:
                nums1[tail] = nums2[nums2Index]
                nums2Index -= 1
            tail -= 1

解决方案2(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) {
        vector<int> result;
        int i = 0, j = 0;
        
        while(i < m && j < n) {
            if(nums1[i] <= nums2[j]) {
                result.push_back(nums1[i++]);
            }else {
                result.push_back(nums2[j++]);
            }
        }
        while(i < m) {
            result.push_back(nums1[i++]);
        }
        
        while(j < n) {
            result.push_back(nums2[j++]);
        }
        nums1 = result;
    }
};

在评论区里有人 po 了一个比较hack的做法：

1
2
3
4
5
6
7
8
9
class Solution {
public:
    void merge(vector<int>& nums1, int m, const vector<int>& nums2, int n) {
        std::merge(
            nums1.rbegin() + (nums1.size() - m), nums1.rend(),
            nums2.rbegin() + (nums2.size() - n), nums2.rend(),
            nums1.rbegin(), greater<int>());
    }
};

当然，最好的情况是不增加空间复杂度，要合并两个有序的数组，可以从后往前写，这样就可以不覆盖 nums1 的元素：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    if (n <= 0) {
        return;
    }
    for(int i = m-1, j = n-1, k = m+n-1; j >= 0; )
        if(i >= 0 && nums1[i] >= nums2[j]) {
            nums1[k--] = nums1[i--];
        }else {
            nums1[k--] = nums2[j--];
        }
    }
};

OMG，在评论区惊现王垠？？？2-lines-very-simple-c-solution

1
2
3
4
5
6
7
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    for(int i=m-1, j=n-1, k=m+n-1; j>=0; )
        nums1[k--] = i>=0 && nums1[i]>nums2[j]? nums1[i--]: nums2[j--];
    }
};

解决方案3（Golang）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func merge(nums1 []int, m int, nums2 []int, n int)  {
    for i := m+n; m > 0 && n > 0; i-- {
        if nums2[n-1] >= nums1[m-1] {
            nums1[i-1] = nums2[n-1]
            n--
        } else {
            nums1[i-1] = nums1[m-1]
            m--
        }
    }
    for ; n-1 >= 0; n-- {
        nums1[n-1] = nums2[n-1]
    }
}

相关问题

题目来源