我在Reddit上看到了这个问题,并没有提出积极的解决方案,我认为这是一个完美的问题.这是关于面试问题的一个主题:
编写一个采用大小为m的int数组的方法,如果数组由数字n ... n + m-1组成,则返回(True/False),该范围内的所有数字以及该范围内的数字.不保证数组已排序.(例如,{2,3,4}将返回true.{1,3,1}将返回false,{1,2,4}将返回false.
我遇到的问题是我的采访者一直要求我优化(更快的O(n),更少的内存等),他声称你可以在数组的一次传递中使用恒定量的记忆.从未想过那一个.
除了您的解决方案,请指出他们是否认为该阵列包含唯一的项目.同时指出您的解决方案是否假设序列从1开始.(我稍微修改了一下这个问题以允许它变为2,3,4 ......)
编辑:我现在认为在空间算法中不存在处理重复的线性时间和常数.任何人都可以验证吗？
重复问题归结为测试以查看数组是否在O(n)时间,O(1)空间中包含重复项.如果可以这样做,您可以先测试,如果没有重复,则运行算法.那么你可以在O(n)时间O(1)空间中测试欺骗吗？