数组中的同一个对是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)
用于排序数组中的线性扫描计数。
您部分正确。通过合并排序或堆排序对数组进行排序将需要O(n lg n)
。但是,对数组进行排序后,您可以单遍查找所有相同的对。此单遍O(n)
操作是一项操作。因此,总复杂度为:
O(n lg n + n) = O(n lg n)
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句