第一缺失正
和往常一样，请对我的代码进行残酷的坦诚，如果我在一家顶级科技公司进行面试(比如谷歌、微软、Facebook等)，你会如何判断它。我的算法的时间复杂度为O(n)。
问题:给定一个未排序的整数数组，查找第一个缺少的正整数。例如,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.* 我的代码(在22分钟内编码，所有测试用例都通过了，在2-5分钟内设计了初始算法)。
public int firstMissingPositive(int[] A) {
int minVal=0;
if(A.length==0){
return 1;
}
Hashtable<Integer, Integer> myTable = new Hashtable<Integer, Integer>();
for(int i : A){
if(i<minVal && i>0){
minVal = i;
}
myTable.put(i, i);
}
for(int i=0; i<=A.length; i++){
if( (!myTable.containsKey(minVal-1)) && minVal-1>0){
return minVal-1;
}
else if(!myTable.containsKey(minVal+1)){
return minVal+1;
}
minVal++;
}
return minVal;
}回答 3
Code Review用户
发布于 2014-03-08 21:41:58
对于使用HashMap，我不得不反对palacsint，如果有的话，我认为您应该使用Set实现，比如HashSet。您从未使用存储在映射中的值，也没有理由使用它。因此，我将使用Set。( HashSet内部使用HashMap是一个完全不同的主题) Palacsint是正确的，尽管HashMap是比Hashtable更好的选择。
读这样的台词让我晕船：
if( (!myTable.containsKey(minVal-1)) && minVal-1>0){适当地使用间隔并删除不必要的参数，它将变成：
if(!myTable.containsKey(minVal - 1) && minVal - 1 > 0) {总的来说，我认为您不应该为此使用对象(当然，数组除外，这在技术上是一个对象)。我会只使用原语和使用更多的自记录变量名。。
代码中的一个不必要的操作是，在每次迭代中，您要检查两次containsKey。一次查看是否设置了value - 1，一次查看是否设置了value + 1。为什么不直接检查值本身是否被设置呢？
您的代码可以重写并优化为：(这是ChrisW方法的固定版本，我是在他发布答案时开始使用的，然后我做了一些修改以确保它与您的代码匹配)。
public int firstMissingPositive(int[] array) {
boolean[] foundValues = new boolean[array.length];
for (int i : array) {
if (i > 0 && i <= foundValues.length)
foundValues[i - 1] = true;
}
for (int i = 0; i < foundValues.length; i++) {
if (!foundValues[i]) {
return i + 1;
}
}
return foundValues.length + 1;
}Code Review用户
发布于 2014-03-08 22:04:49
Re.问题是，我认为0不是正整数？在面试中，您可能会查找规范中的漏洞/歧义，并询问它们(在编写代码之前，请反复检查是否了解需求)。
Re.您的代码，从好的方面来说，在使用散列方面做得很好吗？因为每次查找的哈希往往是O(1)，所以总体上是O(n)。
我看不出你怎么能比O(n)做得更好，因为你需要看每一个项目。
不利的一面是，我认为我看到了一个更简单的实现，如下所示(伪代码，因为我不懂Java)：
public int firstMissingPositive(int[] A) {
{
int length = A.Length;
// create a vector of length 'length'
Vector<bool> vector = new Vector<bool>(length);
// this loop isn't necessary if Vector's elements are default-initialized (to false)
for (int i = 0; i < length; ++i)
vector[i] = false;
// remember what the interesting input integers are
foreach (a in A)
{
if (a > 0) && (a <= length)
vector[a-1] = true;
// else a is not a candidate
}
for (int i = 0; i < length; ++i)
{
if (!vector[i])
// i+1 was not in the input array
return i+1;
}
return length+1;
}我认为我的解决方案更容易阅读；而且可能更快，内存也更少(因为我猜Vector<boolean>比HashSet<int>更简单，占用的空间也更少)。
如果我在一家顶级科技公司为面试做编码，你会怎么判断？
假设在面试中编写代码的原因之一是为了给我们一些可以谈论的东西，看看你如何回应批评，你是否能得到一个更好的答案，你是否能深入理解你选择使用的工具，我可能会问你在构建一个initialCapacity和loadFactor时是否应该指定HashSet和loadFactor，以及这会产生什么效果；并给出一些关于最佳解决方案的提示(作为一次面试，我可能已经知道‘不公平’了，因为我事先被查过了)，看看你是否能得到它。
Code Review用户
发布于 2014-06-05 14:23:46
还有一个我可以考虑使用treeSet的实现。代码有点容易阅读和放入一些边缘情况检查，以提高性能。这可能不会给出O(N)的性能，但会给出O(Nlog N)，因为treeSet插入对于每个插入都是O(log )。但其优势是从treeSet中检索元素。
public static int firstMissingPositive(int[] ip) {
if (ip == null || ip.length == 0) {
return 1;
}
TreeSet<Integer> postiveElements = new TreeSet<Integer>();
for (int e : ip) {
if (e > 0) {
postiveElements.add(e);
}
}
int tsSize = postiveElements.size();
if (tsSize == 0 || postiveElements.first() > 1) {
return 1;
}
if (tsSize == postiveElements.last()) {
return tsSize+1;
}
int incElement = 1;
for(; incElement <= tsSize; incElement++) {
if (incElement != postiveElements.pollFirst()) {
break;
}
}
return incElement;
}https://codereview.stackexchange.com/questions/43813
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号