请设计一个算法, 将两个有序数组合并为一个数组, 请不要使用concat以及sort方法

JavaScript

可以使用双指针法来合并两个有序数组。具体步骤如下：

  1. 创建一个新的数组来存储合并后的结果。
  2. 初始化两个指针，分别指向两个数组的起始位置。
  3. 比较两个指针所指向的元素，将较小的元素添加到新数组中，并将对应指针向后移动一位。
  4. 重复步骤3，直到其中一个数组的指针超出了数组的范围。
  5. 将剩余的未合并元素直接添加到新数组的末尾。
  6. 返回新数组作为结果。

以下是用 JavaScript 实现的代码：

function mergeArrays(arr1, arr2) {
  const merged = [];
  let i = 0; // 第一个数组的指针
  let j = 0; // 第二个数组的指针

  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] <= arr2[j]) {
      merged.push(arr1[i]);
      i++;
    } else {
      merged.push(arr2[j]);
      j++;
    }
  }

  // 将剩余的未合并元素添加到新数组的末尾
  while (i < arr1.length) {
    merged.push(arr1[i]);
    i++;
  }

  while (j < arr2.length) {
    merged.push(arr2[j]);
    j++;
  }

  return merged;
}

// 示例
const arr1 = [1, 3, 5, 7];
const arr2 = [2, 4, 6, 8];
const mergedArray = mergeArrays(arr1, arr2);
console.log(mergedArray); // 输出 [1, 2, 3, 4, 5, 6, 7, 8]

这个算法的时间复杂度是 O(n)，其中 n 是两个数组的总长度。