给定一个值数组，我想找到总“分数”，其中每个元素的分数是数组中出现在其之前的具有较小值的元素的数量。
e.g.
values: 4 1 3 2 5
scores: 0 0 1 1 4
total score: 6
O(n^2) 算法很简单，但我怀疑可以通过对数组进行排序来在 O(nlgn) 中完成它。有谁知道如何做到这一点，或者如果不可能的话？
看起来您所做的本质上是计算相对顺序不正确的元素对的数量（即倒转）。这可以通过使用与合并排序相同的思想在 O(n*log(n)) 中完成。合并时，您只需计算左侧列表中但本应位于右侧列表中的元素数量（反之亦然）。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
