我遇到了一个有趣的算法问题:
给定一个整数数组，找出该数组中无序对的数量，比如给定 {1, 3, 2}，答案是 1，因为 {3, 2} 是无序的，对于数组 { 3, 2, 1}，答案是 3 因为 {3, 2}, {3, 1}, {2, 1}.
显然，这可以通过 O(n^2) 运行时间的蛮力解决，或者置换所有可能的对，然后消除那些无效的对。
我的问题是，是否有人有更好的解决方案，您会怎么做，因为它看起来像是一个动态规划问题。一段代码会有帮助
最佳答案
使用平衡二叉搜索树可以在 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
关于arrays - 查找数组中无序对的数量，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26702051/