88. Merge Sorted Array
給定兩個按非遞減順序排序的整數數組 nums1 和 nums2，以及兩個整數 m 和 n，分別表示 nums1 和 nums2 中的元素數量。
將 nums1 和 nums2 合併成一個按非遞減順序排序的單一數組。
最終排序的數組不應由函數返回，而是應存儲在 nums1 數組內。為了容納這些元素，nums1 的長度為 m + n，其中前 m 個元素表示應合併的元素，最後的 n 個元素設置為 0，應忽略。nums2 的長度為 n。
範例 1：
輸入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 輸出：[1,2,2,3,5,6] 解釋：我們合併的數組是 [1,2,3] 和 [2,5,6]。 合併的結果是 [1,2,2,3,5,6]，其中下劃線的元素來自 nums1。
Python
from typing import List
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.
"""
# Start from the end of nums1 and nums2
p1 = m - 1 # Pointer for the last element in the initial part of nums1
p2 = n - 1 # Pointer for the last element in nums2
p = m + n - 1 # Pointer for the last position in nums1
# While there are elements to compare
while p1 >= 0 and p2 >= 0:
if nums1[p1] > nums2[p2]:
nums1[p] = nums1[p1]
p1 -= 1
else:
nums1[p] = nums2[p2]
p2 -= 1
p -= 1
# If there are remaining elements in nums2, copy them
while p2 >= 0:
nums1[p] = nums2[p2]
p2 -= 1
p -= 1
16.47MB, 43ms
C++
#include <vector>
using namespace std;
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int p1 = m - 1; // Pointer for the last element in the initial part of nums1
int p2 = n - 1; // Pointer for the last element in nums2
int p = m + n - 1; // Pointer for the last position in nums1
// While there are elements to compare
while (p1 >= 0 && p2 >= 0) {
if (nums1[p1] > nums2[p2]) {
nums1[p] = nums1[p1];
p1--;
} else {
nums1[p] = nums2[p2];
p2--;
}
p--;
}
// If there are remaining elements in nums2, copy them
while (p2 >= 0) {
nums1[p] = nums2[p2];
p2--;
p--;
}
}
};
11.00MB, 0ms
Javascript
/**
* @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; // Pointer for the last element in the initial part of nums1
let p2 = n - 1; // Pointer for the last element in nums2
let p = m + n - 1; // Pointer for the last position in nums1
// While there are elements to compare
while (p1 >= 0 && p2 >= 0) {
if (nums1[p1] > nums2[p2]) {
nums1[p] = nums1[p1];
p1--;
} else {
nums1[p] = nums2[p2];
p2--;
}
p--;
}
// If there are remaining elements in nums2, copy them
while (p2 >= 0) {
nums1[p] = nums2[p2];
p2--;
p--;
}
};
49.05MB, 61ms
