java之一个算法的大O分析——求职面试

最近我有一个面试问题，要编写一个分析数组并返回重复数字的算法；

我的暴力解决方案是:

    public static ArrayList getDuplicates  (int[] input){ 
        ArrayList duplicates =  new ArrayList(); 
        int marker = 0; 
        for (int i = marker + 1; (i < input.length) && (marker < input.length - 1); i++){ 
            if (input[marker] == input[i]){ 
                duplicates.add(input[marker]); 
                marker++; 
                continue; 
            } else { 
                if (i == input.length - 1){ 
                    marker++; 
                    i = marker; 
                } 
                continue; 
            } 
        } 
        return duplicates; 
    }  

没有深入分析我就回复说大O是n*(log(n))。

面试后我再次核对，发现答案不正确。

令人困惑的部分是算法重复，但不是重复 n 次，而是每个循环重复 n-k 次，其中 k = {1..n-1}。这是重置移动索引的部分:

                if (i == input.length - 1){ 
                marker++; 
                i = marker; 
            } 

分析此算法以找到正确的大 O 函数的最佳方法是什么？

请您参考如下方法:

我的分析方法是插入边缘案例，然后查看是否出现任何模式:

1. 如果你有一个包含所有匹配项的数组会怎样？ 在这种情况下，它是 O(N)，因为您每次都点击了重复项的第一个条目。
2. 如果没有重复呢？ 然后，你扫描整个数组 N^2/2 次，所以 O(N^2)

由此，我们可以看出最好的情况是 O(N)，最差的情况是 O(N^2)，我还要说平均情况也将是 O(N^2)

如果您使用嵌套 for 循环，一个用于原始数据扫描，一个用于重复扫描，N^2 行为会更容易发现。

相反，如果您将每个条目添加到具有 O(1) 添加能力的容器(哈希表)，那么您的算法会变得更加简单:

1. 对于输入数组中的每个项目，尝试将值添加到哈希表。
2. 如果该值已存在于哈希中，则插入重复数组。
3. 完成 foreach 扫描并返回重复数组。