合并排序数组 | 简单级-算法

[OBKoro1]

博客链接

# 合并排序数组

# 难度：简单

# 描述：

合并两个排序的整数数组 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. 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;
};

# 点个Star支持我一下~

博客链接