我对Codility MissingInteger的Java解决方案有什么问题？ [英] What is wrong with my Java solution to Codility MissingInteger?

问题描述

我正在尝试解决密码问题MissingInteger问题链接：

I am trying to solve the codility MissingInteger problem link:

写一个函数：

Write a function:

class Solution { public int solution(int[] A); }

给定N个整数的非空零索引数组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] = 2

该函数应返回5.

假设：

N是[1..100,000]范围内的整数;
数组A的每个元素都是[-2,147,483,648..2,147,483,647]范围内的整数。

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].

复杂性：

预期的最坏情况时间复杂度为O（N）;
预期的最坏情况空间复杂度为O（N），超出输入存储（不计入输入参数所需的存储空间）。
可以修改输入数组的元素。

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 {
    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;

    }
}

测试结果是：

任何人都可以解释为什么我得到这两个错误的答案吗？特别是第一个，如果数组中只有一个元素，那么唯一正确答案应该是1？

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?

推荐答案

返回A中没有出现的最小正整数。

returns the minimal positive integer that does not occur in A.

因此，在只有一个元素的数组中，如果该数字为1，则应返回2.如果不是，则应返回1.

So in an array with only one element, if that number is 1, you should return 2. If not, you should return 1.

我想你可能会误解这些要求。您的代码正在基于给定数组的索引在地图中创建键，然后根据它在那里找到的值删除键。这个问题不应该与数组的索引有任何关系：它应该只返回给定数组中不是值的最低正整数。

I think you're probably misunderstanding the requirements a little. Your code is creating keys in a map based on the indexes of the given array, and then removing keys based on the values it 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.

所以例如，如果从 1 迭代到 Integer.MAX_VALUE （包括），并返回第一个值为'n'的值在给定的数组中，这将产生正确的答案。您需要确定要使用的数据结构，以确保您的解决方案可以在 O（n）进行扩展。

So, for example, if you iterate from 1 to 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).

这篇关于我对Codility MissingInteger的Java解决方案有什么问题？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！