算法 - 在 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

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