让我猜测的一个问题如下:
假设我们有一个包含数字 {1,1,1,1,2,2,4,4,4} 的排序数组。
现在,假设我们可以清楚地看到我们有六对 1,一对 2 和三对 4(10 对)。你将如何构建一个算法来在 O(n) 中找到这些对?
我有一个算法来计算数组中的对,并且这样做是这样的:
Arrays.sort(array);
int counter = 0;
for(int i = 0; i<array.length; i++) {
for(int j = i+1; j<array.length; j++) {
if(j!=i && array[j] == array[i]) {
counter++;
}
}
}
return counter;
但这在 O(N^2) 中运行,我猜想(作为算法的新手)是否有更好的解决方案来仅使用一个 for 循环或多个 while 循环来获得相同的结果?
我想听听你的想法!
最佳答案
你可以在 O(N)
中完成:
int pairs = 0;
int times = 1;
for (int i = 1; i < array.length; ++i) {
if (array[i] == array[i-1]) {
++times;
} else {
pairs += times*(times-1) / 2;
times = 1;
}
}
pairs += times*(times-1) / 2;
return pairs;
对于每个不同的数字,计算其出现的次数 time
。不同对的数量等于选择的数量 C(times, 2) = times*(times-1)/2
。
关于java - 算法 - 在 O(n) 中计算排序数组中所有相等数字对?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46425980/