找到数组中 (i,j) 对的总数，使得 i<j 和 a[i]>a[j] [英] find total number of (i,j) pairs in array such that i&lt;j and a[i]&gt;a[j]

问题描述

正如问题中提到的，需要在数组中找到 (i,j) 对的总数，使得

As mentioned in the question ,need to find total number of (i,j) pairs in array such that

(1) **i<j** 
(2) **a[i]>a[j]**

其中 i 和 j 是数组的索引.没有空间限制.

where i and j are indices of the array . There are no space constraints .

我的问题是

 1) Is there any approach which takes less than O(N^2) time?
 2) if so what is least complexity ?
 3) How do we prove that ? 

我希望我对这个问题很清楚.

I hope i'm clear with the question .

我的做法如下

解决这个问题的一种方法是使用需要 O(N^2) 时间的 brute fore.

One way of doing the question is using brute fore which takes O(N^2) time .

但是我觉得这个问题应该有更好的优化解决方案--least O(NlogN) sollution .我的直觉的原因如下

But I think that there should be a better optimised solution to this question at-least O(NlogN) sollution .The reason for my intuition is as follows

直觉1) 对于以升序条件对数组进行排序，我们有:对于 i<j ， a[i]<a[j] 这类似于我的问题.我还读到排序的下限是 Omega(n log n) .所以我的问题也应该有 Omega(n log n) .如果是这样，我可能完全错了，请纠正我.

我的第二个直觉是:

假设我们有一个元素数组如下:4,9,7,3,2,1,8,12

Suppose we have an array of elements as follows : 4,9,7,3,2,1,8,12

我们计算元素4的上述条件ia[j]，因为i=0指向4，j的可能值为3,4，5 .因为 a[0]>a[3],a[0]>a[4],a[0]>a[5] ，所以我现在的 (i,j) 对总数是 3 .下次当我将 i(index) 增加到 1 时， j 的可能值为 2,3,4,5,6 .但是我们应该使用这样一个事实，即当 i=0(当 a[i]=4)时，我们计算了 3 个小于 a[i=0] 的元素，而 a[i=0] 又小于 a[i=1] ，所以我不会将 9 与 3,2,1 进行比较(移除不必要的计算).如果我们可以移除不必要的计算，那么我们可以将复杂度降低到小于 O(N^2) 的程度，否则不存在小于 O(N^2) 的解决方案.但是如果存在解决方案，那么我们该怎么做.我尝试制作图表，但我的努力是徒劳的.

we calculate above condition i<j , a[i]>a[j] for element 4 ,as i=0 points to 4 ,the possible values for j are 3,4,5 .since a[0]>a[3],a[0]>a[4],a[0]>a[5] ,so my total no of (i,j) pairs for now is 3 . Next time when I increment i(index) to 1,the possibles values of j are 2,3,4,5,6 . But we should use the fact that when i=0 (when a[i]=4) we have computed 3 elements less than a[i=0] which is in turn less than a[i=1] , so i will not compare 9 with 3,2,1 (To remove unnecessary computations ).If we can remove unnecessary computations then we can reduce complexity to something less than O(N^2) or else no solution less than O(N^2) exists.But if solution exists then how do we do that.I tried making graph but my efforts are futile .

方法 1)为了获得 O(nlogn) 复杂度，我认为我们需要围绕快速排序或合并排序进行调整以获得解决方案，但这里的问题是，如果我们对数组进行排序，我们会失去实际位置元素.

方法 2)为了在 O(NlogN) 时间内获得解决方案，我认为使用树我们可以获得优化的解决方案.我没有得到任何线索.

方法 3)如果存在任何 O(N) 时间算法，它应该使用散列.但在这种情况下，简单的散列不起作用.

所以请让我知道以上哪些直觉或方法是正确的(如果正确，哪种方法将导致优化的解决方案以及如何).

So please let me know which of the above intuitions or approaches are correct (If correct which approach will lead to optimised sollution and how).

推荐答案

您可以使用该算法计算倒排对，类似于归并排序，如这里.

You can count inverted pairs with the algorithm, similar to merge sort, as explained here.

这个想法是在计数的同时对数组进行归并排序，每一步改变了多少反转.

The idea is to merge sort the array while counting, how many inversions were changed on each step.

另一种方法是使用订单统计树.您将数组的元素按顺序插入到这棵树中，每次插入后，查看插入元素之前有多少元素大于它.

A different approach is to use an order-statistics tree. You sequentially insert elements of the array into this tree, and after each insertion see, how many elements, preceding the inserted element, are larger than it.

订单统计树的替代方法是可索引跳过列表.

An alternative to order-statistics tree is Indexable skiplist.

两种算法的时间复杂度均为 O(N log N).

Both algorithms have O(N log N) time complexity.

为了获得近似的反演次数，O(N) 时间复杂度是可能的，但有一些限制.我们可以像修改归并排序一样修改桶排序.

To get approximate number of inversions, O(N) time complexity is possible with some limitations. We can modify Bucket sort in the same manner merge sort was modified.

在桶排序的分散"阶段，我们应该估计较大元素的桶中元素的数量，同时在某个桶的末尾插入元素(每个桶中的元素保持原始顺序).

On "scatter" phase of Bucket sort we should estimate number of elements in buckets for larger elements, while inserting element at the end of some bucket (elements in each bucket remain in original order).

在桶排序的排序"阶段，我们应该修改(以相同的方式)排序算法(最有可能是插入排序).在将元素插入到适当的位置时，我们应该计算它跳过了多少其他元素.

On "sort" phase of Bucket sort we should modify (in the same way) sorting algorithm (insertion sort, most likely). While inserting the element into its proper place, we should count over how many other elements it jumped.

至于限制，该算法仅适用于数字(或对象，易于转换为数字)，我们应该提前知道这些数字是如何分布的.所以，如果我们有一个均匀分布的整数数组，这个算法应该可以正常工作.

As for limitations, this algorithm works only with numbers (or with objects, easily convertible to numbers), and we should know in advance how these numbers are distributed. So, if we have an array of uniformly distributed integers, this algorithm should work properly.

这篇关于找到数组中 (i,j) 对的总数，使得 i<j 和 a[i]>a[j]的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！