Java 哈希集与 Arrays.sort

Question

我正在尝试解决以下 'codility' 练习：

给出一个由N个不同整数组成的零索引数组A。该数组包含 [1..(N + 1)] 范围内的整数，这意味着正好缺少一个元素。

您的目标是找到缺失的元素。

写一个函数：

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

给定一个零索引数组 A，returns 是缺失元素的值。

例如，给定数组 A 使得：

  A[0] = 2
  A[1] = 3
  A[2] = 1
  A[3] = 5

函数应该 return 4，因为它是缺少的元素。

假设：

    N is an integer within the range [0..100,000];
    the elements of A are all distinct;
    each element of array A is an integer within the range [1..(N + 1)].

复杂度：

    expected worst-case time complexity is O(N);
    expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).

可以修改输入数组的元素。

我想到了两个解决方案：

1) 给予 100%/100%

class Solution {

    public int solution(int[] A) {
        int previous = 0;
        if (A.length != 0) {
            Arrays.sort(A);
            for (int i : A) {
                if (++previous != i) {
                    return previous;
                }
            }
        }
        return ++previous;
    }
}

2) 给出错误 WRONG ANSWER, got 65536 expected 100001

class SolutionHS {

    public int solution(int[] A) {
        int previous = 0;
        HashSet<Integer> hs = new HashSet<>();
        if (A.length != 0) {
            for (int a : A) {
                hs.add(a);
            }

            for (Integer i : hs) {
                if (++previous != i) {
                    return previous;
                }
            }
        }
        return ++previous;
    }
}

我的问题是：这两种方法（使用 hashset 和 Arrays.sort）不应该以相同的方式工作吗？如果不是，你能告诉我有什么区别吗？

Answer 1

HashSet 未排序，因此当您遍历 Set 的元素时，您不会像代码预期的那样按升序排列它们。如果您使用 TreeSet 而不是 HashSet，您的代码将有效。

如果您将第二个循环更改为：

，HashSet 解决方案将给出正确答案

for (int i = 0; i <= A.length; i++) {
    if (!hs.contains(i)) {
        return i;
    }
}

此循环明确检查相关范围内的每个整数是否出现在 HashSet 和 returns 中，第一个（也是唯一一个）没有出现。

无论如何，您的实现都不符合 O(n) 运行时间和 O(1) space 要求。

为了满足要求的运行时间和 space，您应该计算数组元素的总和，然后从 (A.length+1)*A.length/2 中减去该总和。

Java 哈希集与 Arrays.sort

Java hashset vs Arrays.sort

java

arrays

hashset