攻城獅
Not a programmer 不工程的攻城獅

Not a programmer 不工程的攻城獅

LeetCode Solution, Easy, 88. Merge Sorted Array

合併排序陣列

攻城獅's photo
攻城獅
·May 17, 2022·

Subscribe to my newsletter and never miss my upcoming articles

Play this article

88. Merge Sorted Array

題目敘述

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

Example 1:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].

Example 3:

Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.

Constraints:

  • nums1.length == m + n
  • nums2.length == n
  • 0 <= m, n <= 200
  • 1 <= m + n <= 200
  • -10**9 <= nums1[i], nums2[j] <= 10**9

Follow up: Can you come up with an algorithm that runs in O(m + n) time?

題目翻譯

給定兩個整數陣列 nums1nums2,其中這兩個陣列的元素是以升冪排列。另外分別在給兩個整數參數 mn,代表分別從 nums1nums2 取出的元素數量。將 mn 個元素統一編輯到 nums1 中,並且依照升冪排序。不需要回傳值。所以最後 nums1 應該會要 m + n 的長度。

另外思考看看如何將時間複雜度做到 O(m + n)

解法解析

這題有三種解法,第一種就是很直覺的方式,將兩者先相加後再做排序。這種方式就基本上依靠程式語言內建支援的函數來做排序處理。

Time complexity:O((n+m)log(n+m)) Space complexity:O(n)

剩下兩種方式,因為兩著陣列是已經排序過的,所以利用此條件下,使用 Three Pointers 的解法,其差異只是分別從頭開始遍歷還是從尾部開始遍歷。 Three Pointers 分別指向:m 的數量、n 的數量、要插入 nums1 目前的索引位置。這兩種方式都能達到時間複雜度 O(m+n),但是從頭開始的話,空間複雜度會是 O(m),從尾部的空間複雜度則是 O(1)

解法範例

Go

Merge then sort
func merge(nums1 []int, m int, nums2 []int, n int) {
    for i := 0; i < n; i++ {
        nums1[m+i] = nums2[i]
    }
    sort.Ints(nums1)
}
Three Pointers (Start From the Beginning)
func merge(nums1 []int, m int, nums2 []int, n int) {
    nums1Copy := make([]int, m)
    copy(nums1Copy, nums1)
    var p1, p2 int = 0, 0

    for p := 0; p < n+m; p++ {
        if p2 >= n || (p1 < m && nums1Copy[p1] <= nums2[p2]) {
            nums1[p] = nums1Copy[p1]
            p1++
        } else {
            nums1[p] = nums2[p2]
            p2++
        }
    }
}
Three Pointers (Start From the End)
func merge(nums1 []int, m int, nums2 []int, n int) {
    var p1, p2 int = m - 1, n - 1
    for i := n + m - 1; i >= 0; i-- {
        if p2 < 0 {
            break
        }
        if p1 >= 0 && nums1[p1] > nums2[p2] {
            nums1[i] = nums1[p1]
            p1--
        } else {
            nums1[i] = nums2[p2]
            p2--
        }
    }
}

JavaScript

Merge then sort
/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function (nums1, m, nums2, n) {
    for (let i = 0; i < n; i++) {
        nums1[i + m] = nums2[i];
    }
    return nums1.sort((a, b) => a - b);
};
Three Pointers (Start From the Beginning)
/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function (nums1, m, nums2, n) {
    const nums1Copy = nums1.slice(0, m);
    let p1 = 0, p2 = 0;
    for (let i = 0; i < m + n; i++) {
        if (p2 >= n || (p1 < m && nums1Copy[p1] <= nums2[p2])) {
            nums1[i] = nums1Copy[p1];
            p1++;
        } else {
            nums1[i] = nums2[p2];
            p2++;
        }
    }
};
Three Pointers (Start From the End)
/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function (nums1, m, nums2, n) {
    let p1 = m - 1,
        p2 = n - 1;
    for (let i = n + m - 1; i >= 0; i--) {
        if (p2 < 0) {
            break;
        }
        if (p1 >= 0 && nums1[p1] > nums2[p2]) {
            nums1[i] = nums1[p1];
            p1--;
        } else {
            nums1[i] = nums2[p2];
            p2--;
        }
    }
};

Kotlin


PHP


Python

Merge then sort
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.
        """
        # Write the elements of num2 into the end of nums1.
        for i in range(n):
            nums1[i + m] = nums2[i]

        # Sort nums1 list in-place.
        nums1.sort()
Three Pointers (Start From the Beginning)
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.
        """
        # Make a copy of the first m elements of nums1.
        nums1_copy = nums1[:m]

        # Read pointers for nums1Copy and nums2 respectively.
        p1 = 0
        p2 = 0

        # Compare elements from nums1Copy and nums2 and write the smallest to nums1.
        for p in range(n + m):
            # We also need to ensure that p1 and p2 aren't over the boundaries
            # of their respective arrays.
            if p2 >= n or (p1 < m and nums1_copy[p1] <= nums2[p2]):
                nums1[p] = nums1_copy[p1]
                p1 += 1
            else:
                nums1[p] = nums2[p2]
                p2 += 1
Three Pointers (Start From the End)
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.
        """

        # Set p1 and p2 to point to the end of their respective arrays.
        p1 = m - 1
        p2 = n - 1

        # And move p backwards through the array, each time writing
        # the smallest value pointed at by p1 or p2.
        for p in range(n + m - 1, -1, -1):
            if p2 < 0:
                break
            if p1 >= 0 and nums1[p1] > nums2[p2]:
                nums1[p] = nums1[p1]
                p1 -= 1
            else:
                nums1[p] = nums2[p2]
                p2 -= 1

Rust


Swift


Did you find this article valuable?

Support 攻城獅 by becoming a sponsor. Any amount is appreciated!

Learn more about Hashnode Sponsors
 
Share this

Impressum

As smiple as possible