数组中缺少整数

给定正整数列表，找到不在列表中的最小整数。数组中缺少整数

例如：列表= [7,4,9,1]，答案将是2.

应该是什么最快的算法（无排序）在列表中未计算的最小整数？

注意整数非常大的列表，所以哈希不可能？

来源

2014-01-08 sp1rs

除此之外，如果你有很严重的性能要求，排序之后迭代泡沫应该足够快。请注意，性能比较可能取决于典型的数组大小和整数值。 –

为什么不排序？你可以排序。数组是只读的吗？ –

@dystroy或者如果你在采访中...... – Dukeling

为O（n *的log（n））

其运行在O的最简单的算法（N *的log（n））将是：

排序与快速排序排列为为O（n *的log（n））
迭代通过阵列，并找到它是不在列表中最小的元件，其是最大为O（n）

ö （n）和O（1）额外空间

存在运行在O（n）中的算法。它的工作原理如下：

遍历你的数组。对于每个正数，我将数组[i]的值设置为-1。忽略大于数组大小的值
第二次遍历数组并找到第一个非负数的索引。（O（n））的

来源

2014-01-08 09:50:13

我编辑了我的问题。 – sp1rs

查看应该回答你的问题的编辑 –

如果正数“i”大于数组，那么将不起作用？该算法修复了 – Ishtar

在一般情况下，我会

排序阵列（选择相关的排序取决于您的典型阵列或使用适应性的排序功能）
叠代找到第一个缺失整数的数组

来源

2014-01-08 09:50:16

我编辑了我的问题。 – sp1rs

如果数字是唯一您可以在O（nlogn）中使用二进制搜索。缺失值最多为n。

设置低= 0，高= N，
集A =低+（高至低）之间/ 2
计数值的低和高小于或等于一个
- 如果它是少一半，然后，重复进行高=之间的
计数值的低和高大于
- 如果它小于一半重复FO ř低=一个
否则没有溶液（所有值都在阵列中）

来源

2014-01-08 10:55:56 Ishtar

不应该为这个方法排序数组吗？ –

如果您每次循环遍历整个阵列，则不适用。这就是为什么它是O（nlogn）而不是O（logn） – Ishtar

为什么这比仅仅排序和迭代更好？对于O（n）中的算法，请参阅我的回答 –

// Mark arr[i] as visited by making arr[arr[i] - 1] negative. Note that 
// 1 is subtracted because index start from 0 and positive numbers start from 1 
for(i = 0; i < size; i++) 
{ 
    if(abs(arr[i]) - 1 < size && arr[abs(arr[i]) - 1] > 0) 
     arr[abs(arr[i]) - 1] = -arr[abs(arr[i]) - 1]; 
} 

// Return the first index value at which is positive 
for(i = 0; i < size; i++) 
    if (arr[i] > 0) 
     return i+1; // 1 is added becuase indexes start from 0 
}

2步骤算法以从阵列找到最小的正缺少的元素

我们遍历包含所有正数的数组并标记元素x的存在，我们将索引x处的值的符号更改为负数。如果x>大小，则忽略x。
我们再次遍历数组并打印出具有正值的第一个索引。（请记住，这将是指数+ 1阵列从第0索引开始）

Time: O(n) Space: O(1)

来源

2014-07-01 12:35:50 Jerky

数组中缺少整数

回答

相关问题