4

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

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) 辅助空间中执行此操作（这意味着我们必须分配的唯一数组是我们要返回的数组），或者至少摆脱其中一个上面的三个数组？

4

7 回答 7

5

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

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

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

于 2009-11-04T15:37:28.143 回答
2

好的，所以您将输入数组复制到foo. 使用heapsortfoo在 O(n log n) 时间内就地排序。现在，获取输入数组的第一个元素，并使用二进制搜索foo在 O(log n) 时间内找到它的排名，并将排名插入数组并返回它。ranks

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

于 2009-11-04T15:36:29.160 回答
0

如果您不拥有该数组，我认为不可能在 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]
于 2009-11-04T15:14:24.400 回答
0

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

于 2009-11-04T15:36:00.747 回答
0

也许用一些简单的代码 总结弗洛林的答案（和相关的评论）会很有用。

以下是在 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，等等。（当然，这些等级从零开始，而不是一。）

于 2009-11-05T13:55:58.857 回答
0

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

于 2016-08-22T20:30:41.880 回答
0

我已经用它在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]

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

于 2016-12-27T19:27:11.150 回答