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

符号 阅读:28 2023-08-06 08:31:55 评论:0

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

我的暴力解决方案是:

    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 扫描并返回重复数组。


标签:面试
声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

关注我们

一个IT知识分享的公众号