数组 - 重复扫描程序和算法运行时

Question

我有两个任务要做：

1.） 创建一个算法，以便它检测数组中是否存在重复项（= 相同的数字）（它的运行时越好，我得到的点就越多）。

2.） 分析算法的运行时。

这是我第一个任务的代码（我必须对数组进行排序，以便算法工作得更快/根本有效。为此，我使用了import而不是自己编码。

import java.util.Arrays;
public class Dupescanner
{
    public static void main(String[] args)
    {
        int[] A = {1, 2, 3, 4, 5, 1, 2, 8, 8};
        Arrays.sort(A);
        System.out.println("Following numbers are duplicates:");
        for (int n = 1; n < A.length; n++)
        {
            if (A[n] == A[n - 1])
            {
                System.out.println(A[n]);
            }
        }
    }
}

输出：

Following numbers are duplicates:
1
2
8

那个算法好吗？我想不出比这更快的东西了。或者也许我误解了这项任务，如果你只是说：真 - 有/有重复。假 - 不是...

对于运行时分析，我不确定，但我也尝试了一下：

int[] A = {1, 2, 3, 4, 5, 1, 2, 8, 8};

成本 1

for 循环的成本为 n，if 的成本也为 n。结果将是 n^2 + 1。我也不确定数组排序是否计数，我排除了它。

Answer 1

你的算法O(nlogn)，这里的瓶颈是排序。

循环以线性时间运行。

这实际上是元素独特性问题。

只有当您允许哈希和额外空间时，它才能更有效地解决（在渐近复杂性方面），通过填充哈希表 （ HashSet ），并在迭代时将所有元素插入其中，如果您在迭代时发现欺骗 - 打印它。

int[] array = {1, 2, 3, 4, 5, 1, 2, 8, 8};
Set<Integer> set = new HashSet<>();
System.out.println("Following numbers are duplicates:");
for (int e : array) { 
  if (!set.add(e)) System.out.println("" + e);
}

此线程讨论问题的下限。