java - 算法 - 在 O(n) 中计算排序数组中所有相等数字对？

Question

让我猜测的一个问题如下:

假设我们有一个包含数字 {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 循环来获得相同的结果？

我想听听你的想法!

Answer 1

你可以在 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;       

可运行:https://ideone.com/mu65ie

对于每个不同的数字，计算其出现的次数 time。不同对的数量等于选择的数量 C(times, 2) = times*(times-1)/2。