查找数组中无序对的数量

Question

我遇到了一个有趣的算法问题:

给定一个整数数组,找到该数组中无序对的数量,比如给定{1,3,2},答案是1,因为{3,2}是未排序的,而对于数组{3,2 ,1},答案是3,因为{3,2},{3,1},{2,1}.

显然,这可以通过具有O(n ^ 2)运行时间的强力来解决,或者置换所有可能的对然后消除那些无效对.

我的问题是,任何机构都有更好的解决方案,你会怎么做,因为它看起来像一个动态的编程问题.一段代码会很有帮助

Answer 1

O(n log n)使用平衡二叉搜索树可以及时解决这个问题.这是这个算法的伪代码:

tree = an empty balanced binary search tree
answer = 0
for each element in the array:
     answer += number of the elements in the tree greater then this element
     add this element to the tree