我遇到了一个有趣的算法问题：
给定一个整数数组，找到该数组中无序对的数量，例如给定{1，3，2}，答案为1，因为{3，2}是无序的，对于数组{3，2 ，1}，答案是3，因为{3，2}，{3，1}，{2，1}。
显然，这可以通过运行时间为O（n ^ 2）的蛮力解决，或者置换所有可能的配对，然后消除那些无效的配对。
我的问题是，任何机构都有更好的解决方案，您将如何做，因为这似乎是一个动态编程问题。一段代码会有所帮助
O(n log n)使用平衡的二进制搜索树可以及时解决此问题。这是此算法的伪代码：
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
