arrays - 使用 typescript 计算数组中的反转

Question

几个小时以来，我一直在努力解决这个错误，但似乎无法找到错误所在。

我正在尝试对给定数组中的反转进行计数，并且我的所有测试都通过了，除非使用此数组作为输入 [6, 1, 2, 5, 4, 3]。

逻辑如下；给定数组 A[1...n]，对于每个 i < j，找到所有反转对使得 A[i] > A[j]

我收到的这个数组的数字是 14 个反转，正确答案是 8。

目前的代码是这样的

function mergeCount(left: number[], right: number[]): number {
  let count = 0;
  let leftCounter = 0;
  let rightCounter = 0;

  while (leftCounter < left.length && rightCounter < right.length) {
    if (left[leftCounter] < right[rightCounter]) {
      leftCounter += 1;
    } else {
      count += left.length - leftCounter;
      rightCounter += 1;
    }
  }

  return count;
}

function countInversions(input: number[]): number {
  if (input.length < 2) return 0;

  const middle = Math.floor(input.length / 2);

  const left = input.slice(0, middle);
  const right = input.slice(middle);

  return countInversions(left) + countInversions(right) + mergeCount(left, right);
}

知道我遗漏了什么或我的代码有什么问题吗？

编辑:

所以问题是我在拆分数组时没有对数组进行排序，我只是更新了计数器。我想出的工作解决方案如下

function mergeCount(left: number[], right: number[]): { output: number[]; count: number } {
  let count = 0;
  let leftCounter = 0;
  let rightCounter = 0;
  const output: number[] = [];

  while (leftCounter < left.length && rightCounter < right.length) {
    if (left[leftCounter] < right[rightCounter]) {
      output.push(left[leftCounter]);
      leftCounter += 1;
    } else {
      output.push(right[rightCounter]);
      count += left.length - leftCounter;
      rightCounter += 1;
    }
  }

  return {
    output: output.concat(left.slice(leftCounter)).concat(right.slice(rightCounter)),
    count,
  };
}

function countInversions(input: number[]): { output: number[]; count: number } {
  if (input.length < 2) return { output: input, count: 0 };

  const middle = Math.floor(input.length / 2);

  const { output: left, count: a } = countInversions(input.slice(0, middle));
  const { output: right, count: b } = countInversions(input.slice(middle));
  const { output, count: c } = mergeCount(left, right);

  return { output, count: a + b + c };
}

Answer 1

您链接到的 Python 代码也会对数组进行排序 - 但您没有。这可能会导致错误的答案，因为基于归并排序的反转计数算法要求您在对数组进行排序时也对其进行排序(否则，它使用的快捷方式将无效)。

只需将 left 和 right 合并到您的 mergeCount 函数中，也返回它，它应该可以工作。

下面突出显示的 Python 是您的代码中缺少的内容:

 while i < left_len and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]) # this
            i += 1
        else:
            result.append(right[j]) # and this
            count += left_len - i
            j += 1

---

提供更多关于归并排序反转计数思想的背景:

在合并排序中，我们有两个已排序的部分 H1 和 H2:H1 已排序，H2 已排序.我们有一个合并函数，可以有效地将这两个合并到一个大的排序数组中。

现在，这是(好吧，应该)在 OP 的 while 循环中完成。请注意，如果使用他的符号:

left[leftCounter] > right[rightCounter]

(他的else条件)，那么因为left是排序的，所以leftCounter之后的所有元素也会大于right[rightCounter] ，所以我们有 left.length - leftCounter 反转 - 允许我们一次计数超过 1。

当然，只有当您让归并排序执行它的操作并对数组实际排序时，这才成立。