计算相同对的数量

sreeprasad

数组中的同一个对是2个索引p,q，因此

0<=p<q<N并且array[p]=array[q]其中N是阵列的长度。

给定一个未排序的数组，在数组中找到相同的对数。

我的解决方案是按值对数组进行排序，并跟踪索引。

然后对于p排序数组中的每个索引，计算所有q<N这样的和

sortedarray[p].index < sortedarray[q].index and 
sortedarray[p] = sortedarray[q]

这是正确的方法吗？我认为这将是复杂的

O(N log N) for sorting based on value  +

O(N^2) for counting the newsorted array that satisfies the condition.

这意味着我还在看O(N^2)。有没有更好的办法？

随之而来的另一个想法是，对于每个P二进制搜索，满足条件的所有Q的排序数组。那不会降低第二部分的复杂性吗O(Nlog(N))

这是我的第二部分代码

    for(int i=0;i<N;i++){

                    int j=i+1;

            while( j<N && sortedArray[j].index > sortedArray[i].index &&
                   sortedArray[j].item == sortedArray[i].item){

                        inversion++;
                        j++;
            }
      }
   return inversion;

@Edit：我认为，我误以为第二部分的复杂性O(N^2)。

就像在while循环中的每次迭代中一样，不会对索引0-i的元素进行重新扫描，因此需要线性时间来扫描排序后的数组以计算反转。因此，总复杂度为

O(NlogN)用于排序和O(N)用于排序数组中的线性扫描计数。

蒂姆·比格莱森（Tim Biegeleisen）

您部分正确。通过合并排序或堆排序对数组进行排序将需要O(n lg n)。但是，对数组进行排序后，您可以单遍查找所有相同的对。此单遍O(n)操作是一项操作。因此，总复杂度为：

O(n lg n + n) = O(n lg n)

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。