合并多个有序的数组为一个
昨天面试遇到一个题目，如何合并多个从小到大排列的数组为一个？(后来改为合并2个从小到大排列的数组为1个)这是一道算法题目，因为最近很少刷算法开始有点没思路，最后想到可以利用『从小到大排列』的特性，先将第二个数组的第一个数与第一个数组的数字进行比较找到合适的插入点，并记录下一个数字的索引，然后第二个数组的下一个数字只需要从索引开始继续查找插入点并插入。 时间复杂度是多少？ 我回答的是最佳情况O(n) 最差情况O(n^2) ，其实错了，如果两个数组长度都是n的话，最差情况是O(2n) 因为两个数组各自走完一轮比较就完成了。
后来一想这题目涉及到
- 插入排序
- 归并排序
- leetcode88题 https://leetcode.cn/problems/merge-sorted-array/
下面基于leetcode88题来讲解
暴力sort
js的sort复杂度为O(n*log(n)) 但浏览器可能实现不一样复杂度有差别
/**
* @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) {
var s = nums1.length - 1
for (var i = nums2.length - 1; i >= 0 ; i--) {
nums1[s] = nums2[i]
s--
}
nums1.sort((a,b)=>a-b)
};单指针
从小到大顺序比较大小，一边比较一边插入。复杂度O(m+n)
时间 击败 99.19%使用 JavaScript 的用户
内存 击败 81.02%使用 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) {
nums1.splice(nums1.length - n , n )
var n1Index = 0
for (var i = 0; i< nums2.length; i++) {
while(nums1[n1Index] <= nums2[i]) {
n1Index++
}
nums1.splice(n1Index, 0, nums2[i])
}
};双指针
即设置一个空数组，每次比较两个数组最小的值 取出来放到新数组里面
Tags: