小编Mig*_*y_L的帖子

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

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

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

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