测量阵列的"乱序"

Question

给定一组值,我想找到总的"得分",其中每个元素的得分是在数组之前出现的值较小的元素的数量.

例如

values: 4 1 3 2 5
scores: 0 0 1 1 4
total score: 6

O(n ^ 2)算法是微不足道的,但我怀疑通过对数组进行排序可以在O(nlgn)中进行.有没有人有任何想法如何做到这一点,或者如果不可能？

Answer 1

看起来你正在做的事实上是计算不正确的相对顺序(即反转次数)的元素对的数量.这可以通过使用与合并排序相同的想法在O(n*log(n))中完成.合并时,您只需计算左侧列表中的元素数量,但应该在右侧列表中(反之亦然).