如何使java嵌套循环高效

Question

我目前需要编写一个程序，该程序进行两两比较以在int列表中找到匹配的对，但我能想到的唯一方法是通过嵌套的for循环。有没有办法让时间复杂度变为O(n)而不是嵌套for循环的O(n^2) ?

int[] arr = new int[n];
int total = 0;
for (int i=0; i<n; i++){
for (int j=i+1; j<n; j++){
if (arr[i] == arr[j]){
total++;
}
}
}

Answer 1

看起来你只担心计数。因此，如果修改数组不是问题，那么在O(nlog(n))内应用快速排序，然后在O(n)内计算邻居。

Answer 2

您可以使用具有O(1)复杂度的contains方法的HashSet-因为Integer值的hashCode在Java中分布良好(它只是Integer的值)，您应该始终具有恒定的复杂度

HashSet<Integer> set = new HashSet();
for (int i=0; i<n; i++) {
if(set.contains(arr[i])) {
total++;
} else {
set.add(arr[i]);
}
}

阅读更多:

• 哈希集查找复杂度?

---

还有一个额外的算法可以在这里实现，但它需要一些数据限制(由于您的机器上数组的最大长度)。

可以创建一个int数组yourarray，初始化为0，长度为max(arr) + 1。然后，每次执行yourarray[arr[i]]++时，都会对arr进行迭代，然后对yourarray进行迭代，检查值是否大于1-如果是这样，则意味着该值必须重复

Answer 3

0 (n)解。试试这个。

public static void main(String[] args) {
int[] arr = {0, 1, 2, 3, 4, 3, 2, 3};
int total = arr.length - (int)IntStream.of(arr).distinct().count();
System.out.println(total);
}

输出:

3

Answer 4

我认为你可以使用HashSet来解决这个问题。JAVA中的HashSet不允许插入重复的元素。所以你可以用它来使时间复杂度变成O(n)。

int[] arr = new int[n];
Set<Integer> set = new HashSet<Integer>();
Integer total = 0;
for (int x: arr)
{
if (!set.add(x))
{
total++;
}
}