Хэш-набор Java против Arrays.sort

Я пытаюсь решить следующее упражнение "codility":

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

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

Напишите функцию:

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

что для заданного массива A с нулевым индексом возвращает значение отсутствующего элемента.

Например, дан массив 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 и Arrays.sort) работать одинаково? Если нет, можете ли вы сказать мне, в чем разница?


java arrays hashset
person pshemek    schedule 16.03.2016    source источник
comment
Вы можете просто суммировать элементы, а затем вычесть из ожидаемой суммы.   -  person Thomas Jungblut    schedule 16.03.2016
comment
Ваши коды имеют более высокую временную или пространственную сложность, чем ожидалось. В 1) Время равно O(nlogn) и во 2) Пространстве - O(n)   -  person Priyansh Goel    schedule 16.03.2016

Ответы (1)


arrow_upward
0
arrow_downward

HashSet не сортируется, поэтому, когда вы перебираете элементы Set, вы не получаете их в порядке возрастания, как ожидает ваш код. Если бы вы использовали 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.

person Eran    schedule 16.03.2016