我的Codility MissingInteger Java解决方案有什么问题？
我正在尝试解决密码问题MissingInteger问题链接 ：
写一个函数：
class Solution { public int solution(int[] A); }如果给定N个整数的非空零索引数组A，则返回A中不出现的最小正整数。例如，给定：
A[0] = 1 A[1] = 3 A[2] = 6 A[3] = 4 A[4] = 1 A[5] = 2该函数应返回5。
假使，假设：
N是[1..100,000]范围内的整数; 数组A的每个元素是[-2,147,483,648..2,147,483,647]范围内的整数。
复杂：
预期的最坏情况时间复杂度是O（N）; 预期的最坏情况空间复杂度是O（N），超出输入存储（不计入输入参数所需的存储）。 可以修改输入数组的元素。
我的解决方案是：
class Solution { TreeMap all = new TreeMap(); public int solution(int[] A) { for(int i=0; i<A.length; i++) all.put(i+1,new Object()); for(int i=0; i<A.length; i++) if(all.containsKey(A[i])) all.remove(A[i]); Iterator notOccur = all.keySet().iterator(); if(notOccur.hasNext()) return (int)notOccur.next(); return 1; } }
测试结果如下：
任何人都可以解释我为什么我得到这两个错误的答案？ 特别是第一个，如果数组中只有一个元素，那么唯一正确的答案不应该是1吗？
返回A中不出现的最小正整数
因此，在只有一个元素的数组中，如果该数字为1，则应返回2.如果不是，则应返回1。
我想你可能会误解这些要求。 您的代码是基于给定数组的索引在地图中创建键，然后根据它在那里找到的值删除键。 这个问题不应该与数组的索引有任何关系：它应该只返回给定数组中不是值的最低正整数。
因此，例如，如果从1迭代到Integer.MAX_VALUE （包括），并返回不在给定数组中的第一个值，那将产生正确的答案。 您需要确定要使用的数据结构，以确保您的解决方案在O(n)处扩展。
这是我的答案，得到100/100 。
import java.util.HashSet; class Solution { public int solution(int[] A) { int num = 1; HashSet hset = new HashSet (); for (int i = 0 ; i < A.length; i++) { hset.add(A[i]); } while (hset.contains(num)) { num++; } return num; } }
我做了答案的灵感来自Denes的答案，但更简单。
int counter[] = new int[A.length]; // Count the items, only the positive numbers for (int i = 0; i < A.length; i++) if (A[i] > 0 && A[i] <= A.length) counter[A[i] - 1]++; // Return the first number that has count 0 for (int i = 0; i < counter.length; i++) if (counter[i] == 0) return i + 1; // If no number has count 0, then that means all number in the sequence // appears so the next number not appearing is in next number after the // sequence. return A.length + 1;
返回A中未出现的最小正整数
这里的关键是零不包含在上面（因为它不是正整数）。 因此该函数永远不会返回0.我相信这涵盖了上述两个失败案例。
编辑：由于问题已经改变，因为这写了这个答案不再真正相关
很少有错。 只是最后一行
return 1;
应该读
return A.length + 1;
因为此时你已经找到并删除了从1到A.length的ALL KEYS，因为你有匹配它们的数组条目。 测试要求在这种情况下，您必须返回高于数组A中找到的最大值的下一个整数。所有其他可能性（例如，否定条目，缺少1，缺少1和A.length之间的数字）将通过返回第一个未删除的密钥来涵盖在迭代下找到。 这里的迭代是通过“自然排序”完成的，即1 .. max，默认情况下是TreeMap。 因此，第一个未删除的密钥将是最小的缺失整数。
此更改应使2次不正确的测试再次正常。 所以100％的正确性。
当然，效率是另一回事。 在此处使用TreeMap数据结构会在评估测试结果时带来时间损失。 更简单的数据结构（基本上使用您的算法）会更快。
这种更原始的算法避免了排序并将所有条目> 1复制到长度为100001的新数组上，以便索引x保持值x。 它实际上比Serdar的代码运行得更快，具有中型和大型输入数组。
public int solution(int[] A) { int i = 0, count = 0, N = A.length; int[] B = new int[100001]; // Initially all entries are zero for (i = 0; i < N; i++) // Copy all entries > 0 into array B ... if (A[i] > 0 && A[i] < 100001) { B[A[i]] = A[i]; // ... putting value x at index x in B ... count++; // ... and keep a count of positives } for (i = 1; i < count + 1; i++) // Find first empty element in B if (B[i] == 0) return i; // Index of empty element = missing int // No unfilled B elements above index 0 ... return count + 1; // ... => return int above highest filled element }