最近,我遇到了一道面试题,需要编写一个算法来分析一个数组并返回其中重复的数字;
我的暴力解决方案是:
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;
}
在没有经过彻底分析的情况下,我给出了一个答案:Big O是n*(log (n))。
面试后,我再次核对发现这不是正确的答案。
令人困惑的是算法重复执行,但不是n次,而是每个周期执行n-k次,其中k = {1..n-1}。这是重置移动索引的部分:
if (i == input.length - 1){
marker++;
i = marker;
}
什么是分析该算法以找到正确的大O函数的最佳方法?
ArrayList
?它已经过时了,大约有十年了。如果我是面试官,一旦看到这个,我就会停止关注你的代码,因为我知道你没有资格。 - Servy