?题目来源
?题目描述:
给你两个按 非递减顺序 排列的整数数组 nums1
和 nums2
,另有两个整数 m
和 n
,分别表示 nums1
和 nums2
中的元素数目。
请你 合并 nums2
到 nums1
中,使合并后的数组同样按 非递减顺序 排列。
注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1
中。为了应对这种情况,nums1
的初始长度为 m + n
,其中前 m
个元素表示应合并的元素,后 n
个元素为 0
,应忽略。nums2
的长度为 n
。
nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[j] <= 109
?初始思路:同时循环遍历两个数组,选出较小元素放入新数组。剩下一个没有被遍历完的数组的剩余元素直接拼接到新数组后。
?错误示例:
var merge = function (nums1, m, nums2, n) {
let i = 0,
j = 0,
nums3 = [];
while (i < m && j < n) {
if (nums1[i] <= nums2[j]) {
nums3.push(nums1[i++]);
} else {
nums3.push(nums2[j++]);
}
}
if (i < m) {
nums3 = nums3.concat(nums1.slice(i, m));
}
if (j < n) {
nums3 = nums3.concat(nums2.slice(j, n));
}
nums1 = nums3;
};
nums1 = nums3
不会改变原数组,这样做只是改变了参数nums1指向了nums3的内容,但是原nums1内容并没有改变。
?正确示例1:
var merge = function (nums1, m, nums2, n) {
let i = 0,
j = 0,
nums3 = [];
while (i < m && j < n) {
if (nums1[i] <= nums2[j]) {
nums3.push(nums1[i++]);
} else {
nums3.push(nums2[j++]);
}
}
if (i < m) {
nums3 = nums3.concat(nums1.slice(i, m));
}
if (j < n) {
nums3 = nums3.concat(nums2.slice(j, n));
}
for (let i = 0; i < nums1.length; i++) {
nums1[i] = nums3[i];
}
//nums1.splice(0, nums1.length, ...nums3);
};
直接改变nums1对应的区域的值。
注意使用splice
方法会有一定的空间损耗。
时间复杂度:\(O(m+n)\)。
空间复杂度:\(O(m+n)\)。
?正确示例1可以优化的地方:辅助数组nums3可以不用,我们从后往前遍历,依次选择较大的填入nums1。
?正确示例2:省去nums3
数组
数组nums1长度为m+n,后面有n个空位,我们先将较大的元素从后往前填入nums1,由于空位数恰好等于nums2长度,所以nums1元素不会有丢失风险,当nums1遍历完或nums2遍历完,将可能剩余的nums2全部填入nums1,nums1可能没遍历完这种情况不影响结果。
var merge = function(nums1, m, nums2, n){
let 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--];
}
// nums1.splice(0,j+1,...nums2.slice(0,j+1));
}
时间复杂度:\(O(m+n)\)
空间复杂度:\(O(1)\)
小伙伴们有更好的解法吗?