查找数组中无序对的数量

本文介绍了查找数组中无序对的数量的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

I ran into an interesting algorithm problem:

给出一个整数数组，找到该数组中无序对的数量，例如给定{1，3 ，2}，答案是1，因为{3，2}是无序的；对于数组{3，2，1}，答案是3，因为{3，2}，{3，1}，{2， 1}。

Given an array of integer, find the number of un-ordered pairs in that array, say given {1, 3, 2}, the answer is 1 because {3, 2} is un-ordered, and for array {3, 2, 1}, the answer is 3 because {3, 2}, {3, 1}, {2, 1}.

很明显，这可以通过运行时间为O（n ^ 2）的蛮力解决，或者置换所有可能的配对，然后消除那些无效的配对。

Obviously, this can be solved by brute force with O(n^2) running time, or permute all possible pairs then eliminate those invalid pairs.

我的问题是，任何机构都有更好的解决方案，您将如何做，因为这似乎是一个动态编程问题。代码片段将很有帮助

My question is does any body have any better solution and how would you do it because it seems like a dynamic programming problem. A snippet of code would be helpful

推荐答案

可以在 O（n log n）时间，使用平衡的二叉搜索树。 这是此算法的伪代码：

It is possible to solve this problem in O(n log n) time using a balanced binary search tree. Here is a pseudo-code of this algorithm:

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