给定数组 A，检查 A[i] = i 是否存在任何 i。
我应该比线性时间更快地解决这个问题，这对我来说似乎是不可能的。我想到的解决方案是先在 n*log(n) 时间内对数组进行排序，然后你可以轻松地比线性时间更快地检查。但是，由于数组是未排序的，所以我看不到“有效”的解决方案？
最佳答案
对于任意(未排序的)数组，您不能一个复杂度优于 O(N) 的正确算法。
假设您的解决方案优于O(N)。这意味着该算法必须省略 数组的某些项目，因为扫描所有项目是O(N)。
构造 A 使得所有 i 的 A[i] != i 然后运行算法。
让 A[k] 成为被省略的项目。将k赋值给A[k]，
再次运行算法 - 当需要 k 时，它将返回 no such items。
关于algorithm - 给定一个未排序的数组 A，检查 A[i] = i 是否有效存在，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41198698/