有效地寻找数组中的元素的行列？ [英] 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日志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），但使用该比较我[R [K]]和I [R [j]的]代替正常ř[K]对 - [R [j]的，然后交换在R数组中的值按需要（而不是余数组照例中的值）。

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屋！