使用打字稿计算数组中的反转

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

当前的实现看起来相当复杂。我认为它可以更简单（和准确）。

在外循环中迭代所有元素。我们称索引为 i。在内部循环中，迭代所有大于 i 的元素并将它们与外部索引元素进行比较。

function countInversions(input: number[]): number {
    let count = 0;
    for (let i = 0; i < input.length; i++) {
        for (const num of input.slice(i + 1)) {
            if (input[i] > num) {
                count++;
            }
        }
    }
    return count;
}

Answer 2

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

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

下面突出显示的 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 个以上。

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

使用打字稿计算数组中的反转

Counting inversions in an array with typescript

arrays

algorithm

mergesort

typescript