合并排序数组

难度:简单

描述:

合并两个排序的整数数组 A 和 B 变成一个新的排序数组

样例:

给出A=[1,2,3,4]B=[2,4,5,6],返回 [1,2,2,3,4,4,5,6]

题目分析:

注意 A 和 B 本来就是排序好的数组,最简单的就是用sort排序了。

sort排序

  1. 把两个数组合并成一个数组
  2. 用 sort 升序进行排序。
const mergeSortedArray = function(A, B) {
  let newArr = A.concat(B); // 合并数组
  return newArr.sort((a, b) => {
    return a - b; // sort排序
  });
};
1
2
3
4
5
6

先对比完一个数组:

  1. 初始两个变量分别对应一个数组,进入循环

  2. i 和 j 不会同时递增,只在对应数组元素打败另一数组元素时才会递增,只要打败一个即可,因为两个数组一开始就是排序好的

  3. i 和 j 必须有一个超过对应数组长度(这样至少有一个数组的元素被逐一比较过)

  4. 如果一个数组那边超过长度,会退出循环,但是可能由一方的长度还有剩余(比如一个元素打败另一数组的所有元素),所以我们需要将长度有剩余的数组剩下的元素全都 push 到新数组中(因为一开始就排序好的,后面出场的只会更强)

const mergeSortedArray = function(A, B) {
  var i, j;
  var arr = [];
  for (i = 0, j = 0; i < A.length && j < B.length; ) {
    // i或者j必须有一个超过对应数组长度 才退出循环 所以至少有一个数组的元素被逐一比较
    if (A[i] < B[j]) {
      // 下面两种写法是一样的
      arr.push(A[i]);
      i++;
    } else {
      arr.push(B[j++]); // 这里会先把j赋值给B[j], 然后再j++
    }
  }

  // 上面至少有一个数组已经比较了每个元素 如果还有一方长度有剩余 直接push进来就可以(AB一开始就是排序好的数组)
  while (i < A.length) {
    arr.push(A[i++]);
  }
  while (j < B.length) {
    arr.push(B[j++]);
  }
  return arr;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Last Updated: 9/23/2018, 3:13:25 PM