归并排序
解题思路
归并排序 partition 的过程（将两个有序的数列合并成一个有序数列）；
直观的思路是新建一个新的数列，遍历 nums1 和 nums2 这两个数列，将新建的数列有序后又赋值给 nums1 后返回；
复杂度
-
时间复杂度：
O(m+n) -
空间复杂度：
O(m+n)
代码实现
// 还没整理 归并排序 相关内容，先欠着
尾插法
解题思路
倒序遍历数组 nums1、nums2 ，将最大值放到 nums1 的最后面；
nums1 的后半部分是空的，可以直接覆盖而不会影响结果；
复杂度
-
时间复杂度：
O(m+n)，指针移动单调递减，最多移动 m + n 次，因此时间复杂度为O(m+n) -
空间复杂度：
O(1)，直接对数组 nums1 原地修改，不需要额外空间
代码实现
var merge = function (nums1, m, nums2, n) {
n--;
m--;
let inx = m + n + 1;
while (n >= 0 && m >= 0) {
nums1[inx--] = nums2[n] >= nums1[m] ? nums2[n--] : nums1[m--];
}
while (n >= 0) {
nums1[inx--] = nums2[n--];
}
while (m >= 0) {
nums1[inx--] = nums1[m--];
}
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
115.不同的子序列
上一篇
评论
