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.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/