有效地查找数组中元素的行列? [英] Efficiently finding the ranks of elements in an array?

问题描述

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

How does one find the rank of each element of an array, averaging in the case of ties, efficiently? For example:

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

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

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

The only way I can think of doing it requires allocating 3 arrays:

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

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

Does anyone know how to do this in O(N log N) time and O(1) auxiliary space (meaning the only array we have to allocate is the one we're going to return), or at least get rid of one of the three arrays above?

推荐答案

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

You can allocate the array you are going to return (let's call it R), initialize it to 0..n-1 and then "sort" the incoming array (called I) but using the comparison I[R[k]] vs. I[R[j]] instead of the normal R[k] vs. R[j] and then swapping the values in the R array as needed (instead of the values in the I array as usual).

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

You can implement this indirect sorting using either quicksort or heapsort (or bubblesort but that will mess up your complexity).

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

You only need to allocate one array - and some stack space for the indices.

这篇关于有效地查找数组中元素的行列?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！