这个问题是针对真正的天才的,因为它应该在没有辅助数组的情况下完成 并且必须是最有效率的!
C 程序 - 需要接收一个包含 X 个数字的数组 (假设 X=4 数组:5,4,3,2) 并检查数组是否包含从 0 到 X-1 的所有数字 (如果 X 是 44,则需要检查数组中是否包含 0 到 43 之间的所有数字)。
它必须非常高效 - 我的意思是,在阵列上运行 43 次不是一个选项!
你知道如何做到这一点吗?我花了几个小时试图解决这个问题,但没有成功!!
它必须是 O(n)。
最佳答案
如果允许更改数组的顺序,您可以使用就地排序算法,然后检查是否有一些 i:
array[i] == array[i+1]
时间复杂度可以是O(n*lg n)。
关于c - 数组验证 - 不使用辅助数组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8710316/