如何测量和QUOT;乱序＆QUOT;一个数组 [英] Measuring how "out-of-order" an array is

问题描述

鉴于值的数组，我想找到的总得分，其中每个元素的得分是在它之前发生在阵列中以较小的值元素的数量。

Given an array of values, I want to find the total "score", where the score of each element is the number of elements with a smaller value that occur before it in the array.

例如。

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

这是为O（n ^ 2）算法是微不足道的，但我怀疑有可能做到这一点在O（nlgn），通过排序的数组。没有人有任何想法如何做到这一点，或者如果它是不可能的？

An O(n^2) algorithm is trivial, but I suspect it may be possible to do it in O(nlgn), by sorting the array. Does anyone have any ideas how to do that, or if it's not possible?

推荐答案

看起来你正在做的基本上是计算元素对的是不正确的相对顺序号是什么（即数量的倒）。这可以在O通过使用相同的想法，合并排序完成（的n * log（n））的。当你合并，你只算元素的数量是到左侧列表中，但应该是在他右侧列表中（反之亦然）。

Looks like what you are doing is essentially counting the number of pairs of elements that are in the incorrect relative order (i.e. number of inversions). This can be done in O(n*log(n)) by using the same idea as merge sort. As you merge, you just count the number of elements that are to the left list but should have been on he right list (and vice versa).

这篇关于如何测量和QUOT;乱序＆QUOT;一个数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！