查找数组中无序对的数量 [英] Find the number of unordered pair in an array

问题描述

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

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

这篇关于查找数组中无序对的数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！