让我猜测的一个问题如下：
假设我们有一个排序数组，其中包含数字 {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;
对于每个不同的数字，计算其出现的次数
timesC(times, 2) = times*(times-1) / 2好吧，这也是我的解决方案：
int i = 0;
int pairs = 0;
while (i < array.length - 1) {
if(array[i] == array[i + 1]) {
pairs += 1;
i += 2;
} else {
i++;
}
}
当找到一对时，索引会增加 2，这使得遍历速度更快一些。但无论如何，复杂性是
O(n)当然，你在数组
sorted秘诀就是停止重复。缓存出现的数据。您可以使用缓存将其减少为 O(nlogn) 问题。
“配对”是非常模糊的措辞，因此将来更多的示例将澄清您不知道名称来查找答案的事情。您可以使用组合数学将问题简化为 O(n)。
维基百科文章读起来有点迟钝，但您要查找的方程就在顶部附近：
n! / (k! * (n - k)!)
其中
!
表示阶乘数，
n表示要组合的项目数量（4 个 1），
k表示每个组合的项目数量（2 个为一对）。因此替换这些值：
4! = 24
2! = 2
(4-2)! = 2
4!/(2!2!) = 24/4 = 6
使用这个方程可以将其简化为 O(n)。由于使用了阶乘并对数据集进行了排序，因此您可以通过缓存阶乘调用的结果以供将来调用来进一步提高性能。阶乘函数的排序输入几乎每次查找都会有缓存命中！
如果您使用 python 3，则可能不需要缓存，因为它使用比 python 2 更有效的算法来计算阶乘。缓存将减少冗余，但这可能会在非常大的值上产生良好的结果。
缓存（记忆）的示例：
import math
class Cache(object):
memos = dict()
def factorial(self, n):
if not n in self.memos:
self.memos[n] = math.factorial(n)
return self.memos[n]
Arrays.sort(array);
int counter = 0;
for(int i = 1; i<array.length; i++) {
if(array[i] == array[i-1]) {
counter++;
++i;
}
}
return counter;
static int foo(int[] ar) {
int count = 0;
Arrays.sort(ar);
for(int i = 0; i<ar.length-1;i++)
{
if(ar[i] == ar[i+1])
{
count ++;
i++;
}
}
return count;
}