讨论/面试考题/一个比较简单的数组合并问题/
一个比较简单的数组合并问题

给出三个有序数组,合并成一个并输出。

int[] a1 = new int[] {1, 3, 4};
int[] a2 = new int[] {2, 5, 9};
int[] a3 = new int[] {2, 4, 7, 10};

不能先合完用sort,java的话应该怎么写。

展开讨论
lllOrz发起于 2020-04-11
最近编辑于 2020-04-11

这是一个典型的多路归并问题,我写了个js版本的:

function mergeSortedArr(arrs) {
  let len = 0;
  let indexes = [];
  for (const arr of arrs) {
    len += arr.length;
    indexes.push([0, arr.length]);
  }
  const res = new Array(len);
  let i = 0;
  while (i < len) {
    // 确定最小的数在哪个索引
    let j = 0;
    let minIndex = -1;
    let min = Number.MAX_SAFE_INTEGER;
    while (j < indexes.length) {
      const [start, limit] = indexes[j];
      if (start < limit) {
        if (arrs[j][start] < min) {
          min = arrs[j][start];
          minIndex = j;
        }
      }
      j++;
    }
    if (minIndex !== -1) {
      res[i++] = arrs[minIndex][indexes[minIndex][0]++];
    }
  }
  return res;
}

let a1 = [1, 3, 4];
let a2 = [2, 5, 9];
let a3 = [2, 4, 7, 10];
let ret = mergeSortedArr([a1, a2, a3]);
debugger;
2
展开全部 3 讨论