缺少整数变化-需要O（n）解决方案 [英] Missing integer variation - O(n) solution needed

问题描述

问题来自于Codility编程培训，听起来像是：
我们有一个数组（A []​​），其中包含n个元素（范围从1到100,000），这些是我们的参数。数组的元素是从-2,147,483,648到2,147,483,647的整数，我们需要找到不在数组中的最小正整数。当然，这可以在O（n * log n）中轻松完成，方法是将它们全部排序并遍历排序后的数组，寻找丢失的正数（在我的解决方案中，最后一个操作的时间复杂度为O（n））。但是根据Codility，整个问题都可以在O（n）中完成，而我看不到任何解决方法。

The problem comes from Codility programming training and it sounds as follows: we have an array (A[]) with n (ranging from 1 to 100,000) elements and these are our parameters. The elements of the array are integers from −2,147,483,648 to 2,147,483,647, and we need to find smallest positive integer that is NOT in the array. Of course this could be done easily in O(n*log n) by sorting them all and going through the sorted array, looking for the missing posiitve number (this last operation has O(n) worst time complexity in my solution). But according to Codility, this ENTIRE problem can be done in O(n), and I cannot see any way to do that. Could someone give some tips to let me get un-stuck?

PS这是指向我无法复制的问题的详细说明的链接- https://codility.com/c/intro/demo35UEXH-EAT

PS Here is a link to detailed description of the problem which I'm not allowed to copy - https://codility.com/c/intro/demo35UEXH-EAT

推荐答案

根据信鸽原理，数字1、2，...，n + 1中的至少一个不在数组中。
让我们创建一个大小为n + 1的布尔数组 b 来存储是否存在这些数字。

By pigeonhole principle, at least one of the numbers 1, 2, ..., n+1 is not in the array. Let us create a boolean array b of size n+1 to store whether each of these numbers is present.

现在，我们处理输入数组。如果找到从1到n + 1的数字，则会在 b 中标记相应的条目。如果我们看到的数字不适合这些范围，则将其丢弃并继续下一个。两种情况均为每个输入项均为O（1），总计为O（n）。

Now, we process the input array. If we find a number from 1 to n+1, we mark the corresponding entry in b. If the number we see does not fit into these bounds, just discard it and proceed to the next one. Both cases are O(1) per input entry, total O(n).

在完成输入处理后，我们可以找到第一个未标记的项我们的布尔数组 b 在O（n）中很小。

After we are done processing the input, we can find the first non-marked entry in our boolean array b trivially in O(n).

这篇关于缺少整数变化-需要O（n）解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！