有效地查找数组中元素的行列？

Question

如何有效地找到数组中每个元素的排名，在平局的情况下求平均值？例如：

float[] rank(T)(T[] input) {
    // Implementation
}

auto foo = rank([3,6,4,2,2]);  // foo == [3, 5, 4, 1.5, 1.5]

我能想到的唯一方法是分配 3 个数组：

1. 输入数组的副本，因为它必须排序并且我们不拥有它。
2. 一个数组，用于跟踪输入数组的排序顺序。
3. 要返回的行列数组。

有谁知道如何在 O(N log N) 时间和 O(1) 辅助空间中执行此操作（意味着我们必须分配的唯一数组是我们要返回的数组），或者至少摆脱其中之一上面的三个数组？

Answer 1

您可以分配要返回的数组（我们称其为 R），将其初始化为 0..n-1，然后对传入的数组（称为 I）进行“排序”，但使用比较 I[R[k]] vs . I[R[j]] 而不是正常的 R[k] vs. R[j] 然后根据需要交换 R 数组中的值（而不是像往常一样的 I 数组中的值）。

您可以使用快速排序或堆排序（或冒泡排序，但这会弄乱您的复杂性）来实现这种间接排序。

您只需要为索引分配一个数组 - 和一些堆栈空间。