Java HashSet против Arrays.sort

Question

Я пытаюсь решить ниже «codility» упражнение:

с нуля, индексированный массив А, состоящий из N различных целых чисел дано. Массив содержит целые числа в диапазоне [1 .. (N + 1)], что означает, что отсутствует один элемент.

Ваша цель - найти этот недостающий элемент.

Написать функцию:

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

, что при нулевой индексированный массив А, возвращает значение недостающего элемента.

Например, если массив А, что:

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

функция должна возвращать 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) дает ошибку неправильный ответ, получил 65536 ожидал 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 и Array.sort) работать одинаково? Если вы не можете сказать мне, в чем разница?

Answer 1

HashSet не сортируется, поэтому, когда вы перебираете элементы набора, вы не получаете их в порядке возрастания, как ожидает ваш код. Если вы использовали TreeSet вместо HashSet, ваш код будет работать.

HashSet решение даст правильный ответ, если изменить вторую петлю на:

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

Этот цикл явно проверяет, отображается ли каждое целое число в соответствующем диапазоне в HashSet и возвращает первый (и только один), которого нет.

Во всяком случае, обе ваши реализации не соответствуют времени работы O(n) и O(1) Требования к пространству.

Чтобы удовлетворить требуемое время и пространство, вы должны рассчитать сумму элементов массива и вычесть эту сумму из (A.length+1)*A.length/2.