高效地在数组中查找元素的排名？

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（NlogN）时间和O（1）辅助空间（意味着我们只需分配要返回的数组）完成此操作，或者至少消除上述三个数组中的其中一个吗？

- dsimcha

---

“我们不拥有它”是什么意思？ - Jacob

实际上，您可能不需要第二个数组，因为在排序后的数组中查找是O(log N)，您需要进行N次查找，这可以满足O(N log N)的要求。 - Matthieu M.

"we don't own it" = 这是一个库函数，必须假设rank()的调用者不希望他的输入数组被随意重新排序，所以根据最少惊讶原则，我们必须复制它并在副本上进行排序。 - dsimcha

你不能拥有O(1)的辅助空间！由于数组的大小可以变化，因此你必须拥有O(n)的辅助空间。 - rlbond

Answer 1

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

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

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

- florin

---

其实，仔细想想，这个方法行不通。我最初误解了它。 - dsimcha

是的，你需要间接比较，然后也要更新间接数组。我已经在我的帖子中添加了澄清。 - florin

Matthieu：你能解释一下“平均要求”吗？ - florin

正是我要给出的答案。这里是Python的一个示例实现：ranks = sort(range(len(l)), key=lambda x:l[x]) - Nick Johnson

这项技术如何解决重复问题？ - JavaDeveloper

Answer 2

好的，所以你需要将输入数组复制到foo中。使用堆排序在O(n log n)时间内就地对foo进行排序。现在，取出输入数组的第一个元素，并使用二分查找在O(log n)时间内找到它在foo中的排名，并将该排名插入到ranks数组中并返回。

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

- Jacob

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]

- Egon

Answer 4

也许用一些简单的代码总结 Florin's answer（以及相关评论）会很有用。

以下是在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]

排名数组告诉你0的排名为2，1的排名为1，2的排名为4等等。（当然，这些排名从零开始，而不是从一开始。）

- Nate Kohl

---

这种方法不适用于数组中的负元素：尝试使用arr = [5,1,0,3,-2,4] -- 你会得到[4, 2, 1, 3, 5, 0]。 - florin

Answer 5

为什么不直接复制并对数组进行排序呢？有很多原地排序算法可用，例如堆排序。

- rlbond

Answer 6

怎么样使用二叉搜索树，逐个将元素插入到该BST中。通过对BST进行中序遍历，在要查找排名的元素节点左侧保持一个计数器，就可以确定排名。

- user6153549

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]

第一个例子适用于您的原始列表中没有重复项的情况。它可以做得更好，但我正在尝试一些技巧并得出了这个结果。如果您有重复项，则第二个例子将起作用。

- pablora