假设您从一些完全有序的集合中获得了n个不同元素的数组A. 例如,您可能会被给予
137 13 7 42 38
目标是为该元素阵列产生匹配的阵列B,使得B [i]是原始阵列中小于A [i]的元素的数量.例如,在上面的数组中,我们想要生成
A = 137 13 7 42 38
B = 4 1 0 3 2
由于137大于其他四个元素(13,7,42,38),因此13仅大于元素(7)之一,7大于其他元素等.
在最一般的情况下,数组中的元素是只能进行比较的任意对象,在最坏的情况下,此问题的任何解决方案必须以Ω(n lg n)运行,因为一旦我们有了这个表,我们就可以对通过创建n个元素的新数组,然后将每个元素放在表中指定的位置,在O(n)时间内进行数组.但是,我不知道的是,当元素不是任意值时,我们可以多快地构造这个表.
我的问题是这样的:假设你有一个n个不同整数值的数组,并且想要为该数组构造一个顺序统计表.这样做最有效的算法是什么？如果它有帮助,你可以假设整数是正数,并且它们中的最大值具有值U.
目前,我所拥有的最好的是O(n lg n)解决方案,它通过制作数组的副本,对其进行排序,然后对原始数组中的每个整数进行处理,进行二进制搜索以找到它在新数组中的位置.这是一个很好的解决方案,但我真的希望有更好的方法来做到这一点.
第1步:对原始数组索引进行排序.
A = 137 13 7 42 38
I = 0 1 2 3 4
A' = 7 13 38 42 137
I' = 2 1 4 3 0
第2步:为每个I'[i] = j分配B[j] = i.
I' = 2 1 4 3 0
i = 0 1 2 3 4
B = 4 1 0 3 2