Найти недостающий элемент

Question

Я видел следующий вопрос:

Учитывая массив A целых чисел, найдите целое число k, которого нет в A. Предположим, что целые числа являются 32-разрядными целыми числами со знаком.

Как ее решить?

Спасибо

//// update - это предоставленное решение - но я не думаю, что оно правильное //// Рассмотрим очень простой хешфункция F (x) = x mod (n + 1).мы можем построить битовый вектор длиной n + 1, который инициализируется равным 0, и для каждого элемента в A мы устанавливаем бит F (A [i]) в 1. Поскольку в массиве только n элементов, мы можем найтилегко пропустить элемент.

Я думаю, что вышеприведенное решение неверно.

Например, A [2, 100, 4], тогда 4 и 100 будут совпадать в одном месте.

Answer 1

Если я правильно интерпретирую вопрос, (найдите любое целое число не в A) и n - это количество элементов в A, тогда ответ верен, как указано.

Тот факт, что хеш-функция может иметь конфликты, на самом деле не имеет значения; По обратному принципу, в битовом векторе будет некоторый бит, который не установлен - потому что у него больше битов, чем элементов в A. Соответствующее значение является целым числом, а не в A. В случае, когда хеш-функция имеет коллизии, фактически не будет установлено более одного бита, что работает в пользу правильности алгоритма, а не против него.

Чтобы проиллюстрировать, вот как будет работать ваш пример:

A = [2, 100, 4]
n = length(A) = 3
f(x) = x mod 4
map(f,A) = [2, 0, 0]

итоговый битовый вектор будет:

[1,0,1,0]

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

Answer 2

Поскольку, похоже, нет верхних границ или других ограничений:

for (int i = int.MinValue; i <= int.MaxValue; i++)
{
    if (! A.Contains(i))
    {
       // found it !
       break;
    }
}

Answer 3

max (items) + 1

приходит на ум.Конечно, он потерпит неудачу, если один из элементов будет 2 ^ 31-1, а другой - - (2 ^ 32).

В противном случае, сортируйте их и ищите интервал.