给定数组a，检查是否存在[i] = i。
我应该比线性时间更快地解决这个问题，对我来说，这似乎是不可能的。我提出的解决方案是首先在n*log（n）时间中排序数组，然后您可以轻松地检查比线性时间更快。但是，由于阵列未分类，所以我看不到"高效"解决方案？
you 不能具有比O(N)复杂性更好的正确算法，对于任意（unsorted）阵列。
假设您的解决方案比O(N)更好。这意味着该算法必须省略数组的某些项目，因为扫描所有项目是O(N)。
构造A，以便所有i的A[i] != i然后运行算法。令A[k]为已省略的项目。将k分配给A[k]，再次运行该算法 - 预期k时它将返回no such items。
您将使用并行算法获得O（log n）（您没有限制）。只需在ld（n）步骤中启动n个处理器，然后让它们并行检查数组项。