我对 Codility MissingInteger 的 Java 解决方案有什么问题？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/26532081/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
What is wrong with my Java solution to Codility MissingInteger?
提问by Tom
I am trying to solve the codility MissingInteger problem link:
我正在尝试解决 codility MissingInteger 问题链接：
Write a function:
class Solution { public int solution(int[] A); }that, given a non-empty zero-indexed array A of N integers, returns the minimal positive integer that does not occur in A. For example, given:
A[0] = 1 A[1] = 3 A[2] = 6 A[3] = 4 A[4] = 1 A[5] = 2the function should return 5.
Assume that:
N is an integer within the range [1..100,000]; each element of array A is an integer within the range [?2,147,483,648..2,147,483,647].
Complexity:
expected worst-case time complexity is O(N); expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments). Elements of input arrays can be modified.
写一个函数：
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)，超出输入存储（不包括输入参数所需的存储）。可以修改输入数组的元素。
My solution is:
我的解决办法是：
class Solution {
TreeMap<Integer,Object> all = new TreeMap<Integer,Object>();
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;
}
}
The test result is:
测试结果是：
Can anyone explain me why I got this two wrong answers?Especially the first one, if there is only one element in the array, shouldn't the only right answer be 1?
谁能解释一下为什么我得到了这两个错误的答案？尤其是第一个，如果数组中只有一个元素，唯一正确的答案不应该是1吗？
采纳答案by StriplingWarrior
returns the minimal positive integer that does not occur in A.
返回 A 中不出现的最小正整数。
So in an array with only one element, if that number is 1, you should return 2. If not, you should return 1.
所以在只有一个元素的数组中，如果这个数字是 1，你应该返回 2。如果不是，你应该返回 1。
I think you're probably misunderstanding the requirements a little. Your code is creating keys in a map based on the indexesof the given array, and then removing keys based on the valuesit finds there. This problem shouldn't have anything to do with the array's indexes: it should simply return the lowest possible positive integer that isn't a value in the given array.
我想你可能有点误解了要求。您的代码根据给定数组的索引在映射中创建键，然后根据在那里找到的值删除键。这个问题不应该与数组的索引有任何关系：它应该简单地返回不是给定数组中的值的最低可能正整数。
So, for example, if you iterate from 1to Integer.MAX_VALUE, inclusive, and return the first value that isn't in the given array, that would produce the correct answers. You'll need to figure out what data structures to use, to ensure that your solution scales at O(n).
因此，例如，如果您从1to 开始迭代Integer.MAX_VALUE，并返回不在给定数组中的第一个值，则会产生正确的答案。您需要确定要使用的数据结构，以确保您的解决方案可扩展到O(n).
回答by extols
returns the minimal positive integer that does not occur in A
返回 A 中不出现的最小正整数
The key here is that zero is not included in the above (as it is not positive integer). So the function should never return 0. I believe this covers both of your failed cases above.
这里的关键是零不包括在上面（因为它不是正整数）。所以这个函数永远不应该返回 0。我相信这涵盖了你上面的两个失败案例。
edit: due to the fact that question has been changed since this was written this answer isn't really relevant anymore
编辑：由于自从写这篇文章以来问题已经改变，这个答案不再真正相关
回答by Adham
I have done the answer inspired by the answer of Denesbut a simpler one.
我已经完成了受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;
回答by joaoprudencio
回答by Trunk
Very little wrong. Just the last line
错的很少。只是最后一行
return 1;
should read
应该读
return A.length + 1;
because at this point you've found & removed ALL KEYS from 1 to A.length since you have array entries matching each of them. The test demands that in this situation you must return the next integer above the greatest value found in array A. All other eventualities (e.g. negative entries, missing 1, missing number between 1 and A.length) are covered by returning the first unremoved key found under iteration. Iteration here is done by "natural ordering", i.e. 1 .. max, by default for a TreeMap. The first unremoved key will therefore be the smallest missing integer.
因为此时您已经找到并删除了从 1 到 A.length 的 ALL KEYS，因为您有与它们中的每一个匹配的数组条目。测试要求在这种情况下，您必须返回数组 A 中找到的最大值之上的下一个整数。所有其他可能性（例如，负条目、缺少 1、缺少 1 和 A.length 之间的数字）都可以通过返回第一个未删除的键来覆盖在迭代中发现。这里的迭代是通过“自然排序”完成的，即 TreeMap 的默认值是 1 .. max。因此，第一个未删除的键将是最小的缺失整数。
This change should make the 2 incorrect tests okay again. So 50/50 for correctness.
此更改应使 2 个不正确的测试再次正常。所以正确性为 50/50。
Efficiency, of course, is another matter and one that carries another 50 points. Your use of the TreeMap data structure here brings a time penalty when evaluating the test results. Simpler data structures (that essentially use your algorithm) would be faster.
当然，效率是另一回事，另外还有 50 分。在评估测试结果时，您在此处使用 TreeMap 数据结构会带来时间损失。更简单的数据结构（本质上使用您的算法）会更快。
This more primitive algorithm avoids sorting and copies all entries > 1 onto a new array of length 100001 so that index x holds value x. It actually runs faster than Serdar's code with medium and large input arrays.
这种更原始的算法避免了排序并将所有大于 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
}
