给定一个索引为零的数组 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;
}
最佳答案
从您的代码来看,目标似乎是返回 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)
.
关于c# - 在数组中查找升序重复对,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26704355/