Bus*_*ust 8 arrays sorting algorithm asymptotic-complexity
我是第一次通过算法类的分析,并想知道是否有人可以协助下面的例子.我相信我已经解决了它的O(n)复杂性,但是想知道是否有更好的版本,我没有想到O(logn)？
设A = A [1] <= ... <= A [n + 1]是n个不同整数的排序数组,其中每个整数的范围为[1 ... n + 1].也就是说,A中缺少{1,...,n + 1}中的一个整数.描述一个efficeint算法来找到缺失的整数.分析算法的最坏情况复杂性(对数组A的访问次数).
我所拥有的解决方案相对简单,我相信在最坏的情况下会导致N的复杂性.也许我在想这个例子,但有更好的解决方案吗？
我的解决方案
for(i = 1; i < n +1; i++) :
if(A[i-1] > i) :
return i
这背后的逻辑是因为它被排序,第一个元素必须是1,第二个必须是2,依此类推,直到数组中的元素大于它应该是的元素,指示一个元素错过了,返回应该是的元素,我们有失踪的元素.
这是正确的逻辑吗？还有更好的方法吗？
感谢您的阅读并提前感谢您的帮助.
这个逻辑肯定是正确的,但它不足以击败O(n),因为你检查每个元素.
你可以通过观察if A[i]==i,然后所有元素j < i都在适当的位置来更快地完成它.这个观察应该足以构建一个在O(log 2 n)中运行的分而治之的方法:
更正式的是,你正在寻找一个地方A[i]==i和A[i+1]==i+2.您从数组末尾的间隔开始.间隔中间的每个探针将剩余间隔缩小两倍.在某些时候,你只剩下两个元素的间隔.左边的元素是最后一个"正确"元素,而右边的元素是缺少数字后面的第一个元素.