x对数组/列表中的元素进行排序只是为了找出数组/列表中严格小于x的元素数量.
因此,对列表进行排名只是获取列表中所有元素的排名.
例如,rank [51, 38, 29, 51, 63, 38] = [3, 1, 0, 3, 5, 1]即有3个小于51的元素,等等.
可以在O(NlogN)中对列表进行排名.基本上,我们可以在记住每个元素的原始索引的同时对列表进行排序,然后查看每个元素之前的数量.
这里的问题是如何对列表的后缀进行排名O(NlogN)？
对列表的后缀进行排名意味着:
列表[3; 1; 2],等级[[3; 1; 2]; [1; 2]; [2]]
请注意,元素可能不明确.
编辑
我们不需要打印出所有后缀的所有元素.你可以想象我们只需要打印一个列表/数组,其中每个元素都是后缀的等级.
例如,rank suffix_of_ [3; 1; 2] = rank [[3; 1; 2]; [1; 2]; [2]] = [2; 0; 1],你只需打印出[2; 0; 1].
编辑2
让我解释一下所有后缀是什么,这意味着在这里更清楚地排序/排序所有后缀.
假设我们有一个数组/列表[e1; e2; e3; e4; e5].
那么[e1; e2; e3; e4; e5]的所有后缀都是:
[e1; e2; e3; e4; e5]
[e2; e3; …