daily leetcode - merge-sorted-array - !
题目地址
https://leetcode.com/problems/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:
Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
思路
混合插入有序数组，由于两个数组都是有序的，所有只要按顺序比较大小即可。题目中说了 nums1 数组有足够大的空间，说明不用 resize 数组，又给了 m 和 n，那就知道了混合之后的数组的大小，这样就从 nums1 和 nums2 数组的末尾开始一个一个比较，把较大的数，按顺序从后往前加入混合之后的数组末尾。需要三个变量 i，j，k，分别指向 nums1，nums2，和混合数组的末尾。进行 while 循环，如果 i 和 j 都大于 0，再看如果 nums1[i] > nums2[j]，说明要先把 nums1[i] 加入混合数组的末尾，加入后 k 和 i 都要自减 1；反之就把 nums2[j] 加入混合数组的末尾，加入后 k 和 j 都要自减 1。循环结束后，有可能 i 或者 j 还大于等于 0，若 j 大于 0，那么还需要继续循环，将 nums2 中的数字继续拷入 nums1。若是 i 大于等于 0，那么就不用管，因为混合数组本身就放在 nums1 中，参见代码如下：
解法一：
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int i = m - 1, j = n - 1, k = m + n - 1;
while (i >= 0 && j >= 0) {
if (nums1[i] > nums2[j]) nums1[k--] = nums1[i--];
else nums1[k--] = nums2[j--];
}
while (j >= 0) nums1[k--] = nums2[j--];
}
};
我们还可以写的更简洁一些，将两个 while 循环融合到一起，只要加上 i>=0 且 nums1[i] > nums2[j] 的判断条件，就可以从 nums1 中取数，否则就一直从 nums2 中取数，参见代码如下：
解法二：
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int i = m - 1, j = n - 1, k = m + n - 1;
while (j >= 0) {
nums1[k--] = (i >= 0 && nums1[i] > nums2[j]) ? nums1[i--] : nums2[j--];
}
}
};
思路2
符合直觉的做法是将nums2插到num1的末尾, 然后排序
具体代码：
// 这种解法连m都用不到
// 这显然不是出题人的意思
if (n === 0) return;
let current2 = 0;
for(let i = nums1.length - 1; i >= nums1.length - n ; i--) {
nums1[i] = nums2[current2++];
}
nums1.sort((a, b) => a - b); // 当然你可以自己写排序，这里懒得写了，因为已经偏离了题目本身
这道题目其实和基本排序算法中的merge sort非常像，但是 merge sort 很多时候，合并的时候我们通常是
新建一个数组，这样就很简单。 但是这道题目要求的是原地修改.
这就和 merge sort 的 merge 过程有点不同，我们先来回顾一下 merge sort 的 merge 过程。
merge 的过程可以是先比较两个数组的头元素，然后将较小的推到最终的数组中，并将其从原数组中出队列。
循环直到两个数组都为空。
具体代码如下：
// 将nums1 和 nums2 合并
function merge(nums1, nums2) {
let ret = [];
while (nums1.length || nums2.length) {
// 为了方便大家理解，这里代码有点赘余
if (nums1.length === 0) {
ret.push(nums2.shift());
continue;
}
if (nums2.length === 0) {
ret.push(nums1.shift());
continue;
}
const a = nums1[0];
const b = nums2[0];
if (a > b) {
ret.push(nums2.shift());
} else {
ret.push(nums1.shift());
}
}
return ret;
}
这里要求原地修改，其实我们能只要从后往前比较，并从后往前插入即可。
我们需要三个指针：
-
current 用于记录当前填补到那个位置了
-
m 用于记录 nums1 数组处理到哪个元素了
-
n 用于记录 nums2 数组处理到哪个元素了
如图所示：
- 灰色代表 num2 数组已经处理过的元素
- 红色代表当前正在进行比较的元素
- 绿色代表已经就位的元素
关键点解析
- 从后往前比较，并从后往前插入
代码
/*
* @lc app=leetcode id=88 lang=javascript
*
* [88] Merge Sorted Array
*
* https://leetcode.com/problems/merge-sorted-array/description/
*
* algorithms
* Easy (34.95%)
* Total Accepted: 347.5K
* Total Submissions: 984.7K
* Testcase Example: '[1,2,3,0,0,0]\n3\n[2,5,6]\n3'
*
* 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:
*
*
* Input:
* nums1 = [1,2,3,0,0,0], m = 3
* nums2 = [2,5,6], n = 3
*
* Output: [1,2,2,3,5,6]
*
*
*/
/**
* @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) {
// 设置一个指针，指针初始化指向nums1的末尾（根据#62，应该是index为 m+n-1 的位置，因为nums1的长度有可能更长）
// 然后不断左移指针更新元素
let current = m + n - 1;
while (current >= 0) {
// 没必要继续了
if (n === 0) return;
// 为了方便大家理解，这里代码有点赘余
if (m < 1) {
nums1[current--] = nums2[--n];
continue;
}
if (n < 1) {
nums1[current--] = nums1[--m];
continue;
}
// 取大的填充 nums1的末尾
// 然后更新 m 或者 n
if (nums1[m - 1] > nums2[n - 1]) {
nums1[current--] = nums1[--m];
} else {
nums1[current--] = nums2[--n];
}
}
};
模仿上述代码，思路相同
C++ code:
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int current = m + n - 1;
while (current >= 0) {
if (n == 0) return;
if (m < 1) {
nums1[current--] = nums2[--n];
continue;
}
if (n < 1) {
nums1[current--] = nums1[--m];
continue;
}
if (nums1[m - 1] > nums2[n - 1]) nums1[current--] = nums1[--m];
else nums1[current--] = nums2[--n];
}
}
};
Python 代码
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.
"""
# 整体思路相似，只不过没有使用 current 指针记录当前填补位置
while m > 0 and n > 0:
if nums1[m-1] <= nums2[n-1]:
nums1[m+n-1] = nums2[n-1]
n -= 1
else:
nums1[m+n-1] = nums1[m-1]
m -=1
"""
由于没有使用 current，第一步比较结束后有两种情况:
1. 指针 m>0，n=0，此时不需要做任何处理
2. 指针 n>0，m=0，此时需要将 nums2 指针左侧元素全部拷贝到 nums1 的前 n 位
"""
if n > 0:
nums1[:n] = nums2[:n]
本文参考自：
https://github.com/grandyang/leetcode/ &
https://github.com/azl397985856/leetcode
评论
