c - 数组验证 - 不使用辅助数组

Question

这个问题是针对真正的天才的，因为它应该在没有辅助数组的情况下完成并且必须是最有效率的!

C 程序 - 需要接收一个包含 X 个数字的数组(假设 X=4 数组:5,4,3,2)并检查数组是否包含从 0 到 X-1 的所有数字(如果 X 是 44，则需要检查数组中是否包含 0 到 43 之间的所有数字)。

它必须非常高效 - 我的意思是，在阵列上运行 43 次不是一个选项!

你知道如何做到这一点吗？我花了几个小时试图解决这个问题，但没有成功!!

它必须是 O(n)。

Answer 1

如果允许更改数组的顺序，您可以使用就地排序算法，然后检查是否有一些 i:

array[i] == array[i+1]

时间复杂度可以是O(n*lg n)。