问题来自于Codility编程训练,它听起来如下:我们有一个数组(A []),其中n(范围从1到100,000)元素,这些是我们的参数.数组的元素是从-2,147,483,648到2,147,483,647的整数,我们需要找到数组中不存在的最小正整数.当然,这可以在O(n*log n)中轻松完成,方法是将它们全部排序并遍历排序的数组,查找缺少的正数(最后一个操作在我的解决方案中具有O(n)最差的时间复杂度).但根据Codility的说法,这个整体问题可以在O(n)中完成,我看不出有任何办法可以做到这一点.有人可以提供一些技巧让我不被卡住吗？
PS这是一个链接,详细描述了我不允许复制的问题 - https://codility.com/c/intro/demo35UEXH-EAT
algorithm ×1