JS合并两个有序数组

let a = [1, 3, 5, 7, 9]let b = [2, 3, 6, 8, 10]// 输出结果[  1, 2, 3, 3,  5,  6, 7, 8, 9, 10] 这个题目主要考察的是算法,不要直接使用数组的API进行操作, 如下 let result = a.conc...
let a = [1, 3, 5, 7, 9]
let b = [2, 3, 6, 8, 10]
// 输出结果
[
  1, 2, 3, 3,  5,
  6, 7, 8, 9, 10
]


这个题目主要考察的是算法,不要直接使用数组的API进行操作, 如下

let result = a.concat(b).sort((a, b) => a - b)
console.log(result)


这样写并没有利用数组已经排好序的特点,那么这个题怎么解呢?首先第一个数组已经排好序,然后把第二个数组中的元素依次插入到已排序的数组中合适位置,怎么确定这个位置我们可以通过二分查找来处理。

function sort(arrA, arrB) {
  let list = arrA
  for (let i = 0; i < arrB.length; i++) {
    let key = arrB[i]
    insert(list, key)
  }
  return list
}
function insert(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    let mid = (left + right) >> 1;
    if (target < arr[mid]) {
      right = mid - 1
    } else {
      left = mid + 1
    }
  }
  arr.splice(right + 1, 0, target)
  return arr
}


还有其他解法吗?当然有,通过双指针

function solution (num1, num2) {
  let m = num1.length;
  let n = num2.length;
  let p1 = m - 1;
  let p2 = n - 1;
  let p = m + n - 1;
  while (p1 >= 0 && p2 >= 0) {
    num1[p--] = (num1[p1] < num2[p2] ? num2[p2--] : num1[p1--])
  }
  console.log(num1)
  return num1
}


这个解法请参考

https://leetcode-cn.com/problems/merge-sorted-array/solution/tu-jie-he-bing-liang-ge-you-xu-shu-zu-by-user7746o/

你可能感兴趣的文章

相关问题

0 条评论

请先 登录 后评论
王凯
王凯

92 篇文章

作家榜 »

  1. admin 651 文章
  2. 粪斗 185 文章
  3. 王凯 92 文章
  4. 廖雪 78 文章
  5. 牟雪峰 12 文章
  6. 李沁雪 9 文章
  7. 全易 2 文章
  8. Stevengring 0 文章