c# - 在数组中查找升序重复对

Question

给定一个索引为零的数组 A 和 N 个整数，找到数组中不同位置的相等元素。一对索引 (P,Q) 使得 0 <= P < Q < N 使得 A[P] = A[Q]。我的算法如下，但我正在寻找 O(N*logN) 的解决方案。

    public int solution(int[] A)
    {
        int N = A.Length;            
        int count = 0;

        for (int j = 0; j < N; j++)
        {
            count += FindPairs(A[j], j, A);
        }

        return count;
    }

    public int FindPairs(int item, int ci, int[] A)
    {
        int len = A.Length;
        int counter=0;
        int k = ci+1;
        while (k < len)
        {
            if (item == A[k])
                counter++;
            k++;
        }
        return counter;
    }

Answer 1

从您的代码来看，目标似乎是返回 A 中递增重复对的计数。 .

我们观察到如果有m数字 x 的出现次数在 A , 然后是值 x 的递增重复对数是m choose 2 , 或 m (m - 1) / 2 .

所以，我们总结m (m - 1) / 2对于每个独特的 x ，给了我们答案。

在伪代码中，这看起来像:

count = new Dictionary();
foreach a in A {
    count[a]++;
}
total = 0;
foreach key, value in count {
    total += value * (value - 1) / 2;
}
return total;

这个算法是O(N) .