Отсутствует целое число в массиве

Question

Учитывая список положительных целых чисел, найдите наименьшее целое число, которого нет в списке.

Для примера: список = [7,4,9,1], то ответ будет 2.

Каким должен быть быстрый алгоритм (без сортировки) вычислить наименьшее целое число, не в списке ?

Замечательный список целых чисел очень большой, поэтому хеширование невозможно?

Answer 1

O (N * Log (N))

Самый простой алгоритм, который работает в O (N * Log (N)) будет:

• Сортировка массива с Quicksort который O (N * Log (N))
• Итерация через массив и найти наименьший элемент, который не находится в списке, который является максимальным о (п)

O (n) и O (1) дополнительное пространство

Существует алгоритм, выполняющийся в O (n). Работает следующим образом:

• Итерации через ваш массив. Для каждого положительного числа i вы устанавливаете значение в массиве [i] равным -1. Игнорировать значения, превышающие размер массива
• Итерацию второй раз через массив и найти первый индекс, который не является отрицательным. (О (п))

Answer 2

В общем случае, я бы

1. сортировать массив (выбрать соответствующий вид в зависимости от ваших типичных массивов или использовать адаптационную функцию сортировки)
2. итерации над массив, чтобы найти первое отсутствующее целое число

Answer 3

Если номер уникального вы можете использовать бинарный поиск в O (NlogN). Недопустимое значение не более n.

• Установите низкий = 0, высокий = п,
• Набор а = минимум + (высокий-низкий)/2
• значения Count между низким и высоким меньшим или равным
  • если это меньше половины, повторите для высокого = а
• значения Count между низким и высоким больше, чем
  • , если это меньше, чем половина повторения Fo г низкого = а
• Иначе никакого решения (все значения в массиве)

Answer 4

// Mark arr[i] as visited by making arr[arr[i] - 1] negative. Note that 
// 1 is subtracted because index start from 0 and positive numbers start from 1 
for(i = 0; i < size; i++) 
{ 
    if(abs(arr[i]) - 1 < size && arr[abs(arr[i]) - 1] > 0) 
     arr[abs(arr[i]) - 1] = -arr[abs(arr[i]) - 1]; 
} 

// Return the first index value at which is positive 
for(i = 0; i < size; i++) 
    if (arr[i] > 0) 
     return i+1; // 1 is added becuase indexes start from 0 
} 

2 Шаг Алгоритм, чтобы найти наименьший положительный недостающий элемент из массива

1. обходе массив, содержащий все положительные числа, и чтобы отметить присутствие элемента x, мы меняем знак значения с индексом x на отрицательный. Если x> size, то игнорируйте x.
2. Перемещаем массив снова и печатаем первый индекс, который имеет положительное значение. (Помните, что это будет индекс + 1, как массив начинается с 0-го индекса)

Time: O(n) Space: O(1)