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

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]] 与I[R[j]] 而不是普通的 R[k] 与 R[j]，然后根据需要交换 R 数组中的值（而不是像往常一样交换 I 数组中的值）。

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

您只需要分配一个数组 - 以及一些用于索引的堆栈空间。

Answer 2

好的，所以您将输入数组复制到 foo 中。使用 heapsortfoo 进行就地排序一个>。现在，获取输入数组的第一个元素，并使用 foo 中的排名rel="nofollow noreferrer">二分搜索并将排名插入到ranks数组中并返回。

现在，您使用 2 个数组而不是 3 个。

Answer 3

如果您不拥有该数组，我认为不可能在 O(N log N) 和空间 O(1) 中完成它。

如果元素的范围（元素可以有多大）很小，请使用计数。计算每个元素有多少个，然后使用计数数组根据输入数组计算结果数组。

c - is counting result,
C - is cumulative counting
C[i] = c[i] + c[i-1] + c[i-2] + ... + c[0]
result[i] = 1 / c[in[i]] + C[in[i]-1]

Answer 4

为什么不直接复制数组并对其进行排序，然后从那里开始呢？有很多可用的就地排序算法，例如堆排序。

Answer 5

也许总结弗洛林的答案< /a> （以及相关的注释）和一些简单的代码。

以下是在 Ruby 中执行此操作的方法：

arr = [5,1,0,3,2,4]
ranks = (0..arr.length-1).to_a.sort_by{ |x| arr[x] }
# ranks => [2, 1, 4, 3, 5, 0]

在 Python 中：

arr = [5,1,0,3,2,4]
ranks = range(len(arr))
ranks.sort(key=lambda x:arr[x])
# ranks => [2, 1, 4, 3, 5, 0]

ranks 数组告诉您 0 具有排名 2，1 具有排名 1，2 具有排名 4，等等。（当然，这些排名从 0 开始，而不是从 1 开始。）

Answer 6

如何使用二叉搜索树并将元素一一插入到该二叉搜索树中。然后，可以通过对出现在我们想要使用 BST 的按序遍历查找排名的元素节点左侧的所有元素进行计数来确定排名。

Answer 7

我用它在 python 中快速而肮脏地完成了它：

def rank(X):
    B = X[:]
    B.sort()
    return [ float(B.index(x)+1) for x in X]

def rank(X):
    B = X[:]
    B = list(set(B))
    B.sort()
    return [ float(B.index(x)+1) for x in X]

第一个示例在原始列表中没有重复项的情况下有效。它可以做得更好，但我正在玩一些技巧并想出了这个。如果您有重复项，第二个就可以了。