ALE*_*MBS 2 algorithm computer-science
给定数组A,检查A [i] = i是否存在任何i.
我应该比线性时间更快地解决这个问题,这对我来说似乎是不可能的.我想出的解决方案是首先在n*log(n)时间内对数组进行排序,然后您可以轻松地检查比线性时间更快的数据.但是,由于数组未分类,我看不到"有效"的解决方案？
对于任意(未排序)数组,您不能拥有优于O(N)复杂度的正确算法.
假设你有更好的解决方案O(N).这意味着算法必须省略数组的某些项,因为扫描所有项目O(N).
构造A使得A[i] != i对所有人i然后运行算法.我们A[k]是已经省略的项目.分配k给A[k],再次运行算法 - 它会no such items在k预期时返回.