Найдите наименьшее целое число, которого нет в списке

Интересный вопрос из интервью, который использует мой коллега:

Предположим, вам дан очень длинный несортированный список 64-битных целых чисел без знака. Как найти наименьшее неотрицательное целое число, которого нет в списке?

ПОСЛЕДУЮЩИЕ ДЕЙСТВИЯ: Теперь, когда было предложено очевидное решение путем сортировки, можете ли вы сделать это быстрее, чем O (n log n)?

ПОСЛЕДУЮЩИЕ ДЕЙСТВИЯ: ваш алгоритм должен работать на компьютере, скажем, с 1 ГБ памяти.

УТОЧНЕНИЕ: список находится в ОЗУ, хотя может занимать его большой объем. Вам заранее сообщается размер списка, скажем N.

Если структура данных может быть изменена на месте и поддерживает произвольный доступ, вы можете сделать это за O (N) времени и O (1) дополнительного пространства. Просто пройдите по массиву последовательно и для каждого индекса запишите значение индекса в индекс, указанный в value, рекурсивно помещая любое значение в этом месте на его место и отбрасывая значения> N. Затем снова пройдите по массиву в поисках места где значение не соответствует индексу - это наименьшее значение, отсутствующее в массиве. Это приводит к максимуму 3N сравнений и использует только несколько значений временного пространства.

# Pass 1, move every value to the position of its value
for cursor in range(N):
    target = array[cursor]
    while target < N and target != array[target]:
        new_target = array[target]
        array[target] = target
        target = new_target

# Pass 2, find first location where the index doesn't match the value
for cursor in range(N):
    if array[cursor] != cursor:
        return cursor
return N

Вот простое O(N)решение, использующее O(N)пространство. Я предполагаю, что мы ограничиваем входной список неотрицательными числами и хотим найти первое неотрицательное число, которого нет в списке.

1. Найдите длину списка; скажем так N.
2. Выделите массив Nлогических значений, инициализированный для всех false.
3. Для каждого числа Xв списке, если Xменьше, чемN , установите X'thэлемент массива равным true.
4. Просканируйте массив, начиная с индекса 0, в поисках первого найденного элемента false. Если вы найдете первое falseпо индексу I, то Iэто ответ. В противном случае (т.е. когда все элементы есть true) ответ будет N.

На практике «массив Nлогических значений», вероятно, будет закодирован как «битовая карта» или «битовый набор », представленный как массив byteили int. Обычно это занимает меньше места (в зависимости от языка программирования) и позволяет falseбыстрее выполнить сканирование для первого .

Вот как / почему работает алгоритм.

Предположим, что Nчисла в списке неотличимы, или что одно или несколько из них больше, чем N. Это означает, что в диапазоне должен быть хотя бы один номер 0 .. N - 1, которого нет в списке. Таким образом, проблема поиска наименьшего пропущенного числа должна сводиться к проблеме поиска наименьшего пропущенного числа, меньшего, чемN . Это означает, что нам не нужно отслеживать числа, которые больше или равны N... потому что они не будут ответом.

Альтернативой предыдущему абзацу является то, что список представляет собой перестановку чисел из 0 .. N - 1. В этом случае шаг 3 устанавливает для всех элементов массива значение true, а шаг 4 сообщает нам, что первое «отсутствующее» число равно N.

Вычислительная сложность алгоритма O(N)при относительно небольшой константе пропорциональности. Он выполняет два линейных прохода по списку или только один проход, если известно, что длина списка начинается с. Нет необходимости представлять весь список в памяти, поэтому асимптотическое использование памяти алгоритмом - это как раз то, что необходимо для представления массива логических значений; т.е. O(N)биты.

(Напротив, алгоритмы, основанные на сортировке или разделении в памяти, предполагают, что вы можете представить весь список в памяти. В той форме, в которой был задан вопрос, для этого потребовались бы O(N)64-битные слова.)

@Jorn отмечает, что шаги с 1 по 3 являются разновидностью сортировки с подсчетом. В некотором смысле он прав, но различия существенны:

• Для сортировки с подсчетом требуется массив (как минимум) Xmax - Xminсчетчиков, где Xmax- наибольшее число в списке и Xminнаименьшее число в списке. Каждый счетчик должен представлять N состояний; т.е. предполагая двоичное представление, он должен иметь целочисленный тип (как минимум)ceiling(log2(N)) биты .
• Чтобы определить размер массива, сортировка с подсчетом должна выполнить начальный проход по списку, чтобы определить XmaxиXmin .
• Таким образом, минимальная потребность в пространстве для наихудшего случая - ceiling(log2(N)) * (Xmax - Xmin)биты.

Напротив, представленный выше алгоритм просто требует N битов в худшем и лучшем случаях.

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

РЕДАКТИРОВАТЬ: я изменил описание алгоритма, чтобы использовать «массив логических значений», поскольку люди, по-видимому, сочли мое исходное описание с использованием битов и растровых изображений запутанным.

Поскольку OP теперь указал, что исходный список хранится в ОЗУ и что компьютер имеет только, скажем, 1 ГБ памяти, я собираюсь рискнуть и предсказать, что ответ нулевой.

1 ГБ ОЗУ означает, что список может содержать не более 134 217 728 номеров. Но есть 2 ⁶⁴ = 18 446 744 073 709 551 616 возможных чисел. Таким образом, вероятность того, что ноль находится в списке, равна 1 из 137 438 953 472.

Для сравнения, мои шансы на то, что меня ударит молния в этом году, - 1 к 700 000. И мои шансы на попадание метеорита составляют примерно 1 из 10 триллионов. Так что вероятность того, что меня напишут в научном журнале из-за моей безвременной смерти от небесного объекта, примерно в десять раз выше, чем ответ, отличный от нуля.

Как указано в других ответах, вы можете выполнить сортировку, а затем просто сканировать, пока не найдете пробел.

Вы можете улучшить алгоритмическую сложность до O (N) и сохранить пространство O (N), используя модифицированную QuickSort, в которой вы удаляете разделы, которые не являются потенциальными кандидатами на содержание пробела.

• На первом этапе разбиения удалите дубликаты.
• После завершения разделения посмотрите на количество элементов в нижнем разделе.
• Равно ли это значение значению, используемому для создания раздела?
  • Если это так, то это означает, что разрыв находится в верхнем разделе.
    • Продолжайте быструю сортировку, игнорируя нижний раздел
  • В противном случае разрыв будет в нижней перегородке.
    • Продолжите быструю сортировку, игнорируя более высокий раздел

Это экономит большое количество вычислений.

Чтобы проиллюстрировать одну из ловушек O(N)мышления, вот O(N)алгоритм, использующий O(1)пространство.

for i in [0..2^64):
  if i not in list: return i

print "no 64-bit integers are missing"

Поскольку все числа имеют длину 64 бита, мы можем использовать сортировку по основанию для них по , которая равна O (n). Сортируйте их, затем просматривайте, пока не найдете то, что ищете.

если наименьшее число равно нулю, бегите вперед, пока не найдете пробел. Если наименьшее число не равно нулю, ответ равен нулю.

Для экономичного в пространстве метода, и все значения различны, вы можете делать это в пространстве O( k )и времени O( k*log(N)*N ). Он занимает мало места, нет перемещения данных, и все операции элементарны (добавление и вычитание).

1. задавать U = N; L=0
2. Сначала разделите числовое пространство на kрегионы. Как это:
   • 0->(1/k)*(U-L) + L, 0->(2/k)*(U-L) + L, 0->(3/k)*(U-L) + L...0->(U-L) + L
3. Найдите, сколько чисел ( count{i}) есть в каждом регионе. ( N*kшаги)
4. Найдите первый hнеполный регион ( ). Это значит count{h} < upper_limit{h}. ( kшаги)
5. если h - count{h-1} = 1у тебя есть ответ
6. задавать U = count{h}; L = count{h-1}
7. goto 2

это можно улучшить с помощью хеширования (спасибо Нику за эту идею).

1. тем же
2. Сначала разделите числовое пространство на kрегионы. Как это:
   • L + (i/k)->L + (i+1/k)*(U-L)
3. inc count{j} с помощью j = (number - L)/k (if L < number < U)
4. найти первую область ( h), в которой нет k элементов
5. если count{h} = 1ч твой ответ
6. задавать U = maximum value in region h L = minimum value in region h

Это будет работать O(log(N)*N).

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

С точки зрения алгоритма, это можно сделать примерно так:

def smallest_not_in_list(list):
    sort(list)
    if list[0] != 0:
        return 0
    for i = 1 to list.last:
        if list[i] != list[i-1] + 1:
            return list[i-1] + 1
    if list[list.last] == 2^64 - 1:
        assert ("No gaps")
    return list[list.last] + 1

Конечно, если у вас намного больше памяти, чем у процессора, вы можете создать битовую маску всех возможных 64-битных значений и просто установить биты для каждого числа в списке. Затем найдите первый 0-бит в этой битовой маске. Это превращает его в операцию O (n) с точки зрения времени, но чертовски дорого с точки зрения требований к памяти :-)

Я сомневаюсь, что вы могли бы улучшить O (n), так как я не вижу способа сделать это, чтобы не смотреть на каждое число хотя бы один раз.

Алгоритм для этого будет примерно таким:

def smallest_not_in_list(list):
    bitmask = mask_make(2^64) // might take a while :-)
    mask_clear_all (bitmask)
    for i = 1 to list.last:
        mask_set (bitmask, list[i])
    for i = 0 to 2^64 - 1:
        if mask_is_clear (bitmask, i):
            return i
    assert ("No gaps")

Отсортируйте список, посмотрите на первый и второй элементы и начните подниматься вверх, пока не появится пробел.

Вы можете сделать это за O (n) раз и O (1) дополнительного места, хотя скрытый фактор довольно велик. Это непрактичный способ решения проблемы, но, тем не менее, он может быть интересным.

Для каждого 64-битного целого числа без знака (в порядке возрастания) перебирайте список, пока не найдете целевое целое число или не дойдете до конца списка. Если вы дойдете до конца списка, целевое целое число будет наименьшим целым числом, отсутствующим в списке. Если вы дойдете до конца 64-битных целых чисел, каждое 64-битное целое число будет в списке.

Вот это как функция Python:

def smallest_missing_uint64(source_list):
    the_answer = None

    target = 0L
    while target < 2L**64:

        target_found = False
        for item in source_list:
            if item == target:
                target_found = True

        if not target_found and the_answer is None:
            the_answer = target

        target += 1L

    return the_answer

Эта функция намеренно неэффективна, чтобы поддерживать ее O (n). Обратите особое внимание на то, что функция продолжает проверять целевые числа даже после того, как ответ был найден. Если функция вернется, как только ответ будет найден, количество запусков внешнего цикла будет ограничено размером ответа, который ограничен значением n. Это изменение сделает время выполнения O (n ^ 2), хотя это будет намного быстрее.

Спасибо egon, swilden и Stephen C за вдохновение. Во-первых, мы знаем границы ценности цели, потому что она не может быть больше размера списка. Кроме того, список размером 1 ГБ может содержать не более 134217728 (128 * 2 ^ 20) 64-битных целых чисел.

Часть хеширования
Я предлагаю использовать хеширование, чтобы значительно сократить пространство поиска. Сначала извлеките квадратный корень из размера списка. Для списка размером 1 ГБ это N = 11 586. Создайте целочисленный массив размера N. Просмотрите список и возьмите квадратный корень * из каждого найденного числа в качестве хэша. В вашей хеш-таблице увеличьте счетчик для этого хэша. Затем переберите свою хеш-таблицу. Первое обнаруженное вами ведро, не равное максимальному размеру, определяет ваше новое пространство поиска.

Часть растрового изображения
Теперь настройте обычную битовую карту, равную размеру вашего нового пространства поиска, и снова выполните итерацию по исходному списку, заполняя растровое изображение по мере нахождения каждого числа в вашем пространстве поиска. Когда вы закончите, первый неустановленный бит в вашем растровом изображении даст вам ваш ответ.

Это будет выполнено за время O (n) и пространство O (sqrt (n)).

(* Вы можете использовать что-то вроде битового сдвига, чтобы сделать это намного более эффективно, и просто измените количество и размер сегментов соответственно.)

Хорошо, если в списке чисел отсутствует только одно число, самый простой способ найти недостающее число - это просуммировать ряд и вычесть каждое значение в списке. Конечное значение - это пропущенное число.

 int i = 0;
            while ( i < Array.Length)
            {

                if (Array[i] == i + 1)
                {
                    i++;
                }

                if (i < Array.Length)
                {
                    if (Array[i] <= Array.Length)
                    {//SWap

                        int temp = Array[i];
                        int AnoTemp = Array[temp - 1];
                        Array[temp - 1] = temp;
                        Array[i] = AnoTemp;

                    }
                    else
                       i++;



                }
            }

            for (int j = 0; j < Array.Length; j++)
            {
                if (Array[j] > Array.Length)
                {
                    Console.WriteLine(j + 1);
                    j = Array.Length;
                }
                else
                    if (j == Array.Length - 1)
                        Console.WriteLine("Not Found !!");

            }
        }

Мы могли бы использовать хеш-таблицу для хранения чисел. Когда все числа будут выполнены, запустите счетчик от 0 до наименьшего. Достаточно хороший хеш будет хешировать и хранить в постоянное время и извлекать в постоянное время.

for every i in X         // One scan Θ(1)
   hashtable.put(i, i);  // O(1)

low = 0;

while (hashtable.get(i) <> null)   // at most n+1 times
   low++;

print low;

Худший случай, если nв массиве есть элементы, и {0, 1, ... n-1}в этом случае ответ будет получен при nсохранении его O(n).

Вот мой ответ, написанный на Java:

Основная идея: 1. Прокрутите массив, выбрасывая повторяющиеся положительные, нули и отрицательные числа, суммируя остальные, получая максимальное положительное число и сохраняя уникальные положительные числа на карте.

2- Вычислите сумму как max * (max + 1) / 2.

3- Найдите разницу между суммами, рассчитанными на шагах 1 и 2.

4- Выполните цикл снова от 1 до минимума [сумма разницы, макс] и верните первое число, которого нет на карте, заполненной на шаге 1.

public static int solution(int[] A) {
    if (A == null || A.length == 0) {
        throw new IllegalArgumentException();
    }

    int sum = 0;
    Map<Integer, Boolean> uniqueNumbers = new HashMap<Integer, Boolean>();
    int max = A[0];
    for (int i = 0; i < A.length; i++) {
        if(A[i] < 0) {
            continue;
        }
        if(uniqueNumbers.get(A[i]) != null) {
            continue;
        }
        if (A[i] > max) {
            max = A[i];
        }
        uniqueNumbers.put(A[i], true);
        sum += A[i];
    }
    int completeSum = (max * (max + 1)) /  2;
    for(int j = 1; j <= Math.min((completeSum - sum), max); j++) {
        if(uniqueNumbers.get(j) == null) { //O(1)
            return j;
        }
    }
    //All negative case
    if(uniqueNumbers.isEmpty()) {
        return 1;
    }
    return 0;
}

Как разумно заметил Стивен С., ответ должен быть числом меньше длины массива. Тогда я бы нашел ответ с помощью бинарного поиска. Это оптимизирует наихудший случай (чтобы интервьюер не мог поймать вас в патологическом сценарии «что, если»). На собеседовании обязательно укажите, что вы делаете это для оптимизации в худшем случае.

Способ использования двоичного поиска - вычесть искомое число из каждого элемента массива и проверить наличие отрицательных результатов.

Мне нравится метод «нулевого предположения». Если бы числа были случайными, очень вероятно, что ноль. Если «экзаменатор» установил неслучайный список, добавьте его и снова угадайте:

LowNum=0
i=0
do forever {
  if i == N then leave /* Processed entire array */
  if array[i] == LowNum {
     LowNum++
     i=0
     }
   else {
     i++
   }
}
display LowNum

В худшем случае n * N с n = N, но на практике n, скорее всего, будет небольшим числом (например, 1).

Я не уверен, понял ли я вопрос. Но если для списка 1,2,3,5,6 и недостающее число равно 4, то недостающее число можно найти в O (n) следующим образом: (n + 2) (n + 1) / 2- (n + 1) п / 2

РЕДАКТИРОВАТЬ: извините, я думаю, что вчера вечером я слишком быстро думал. В любом случае, вторую часть нужно заменить на sum (list), откуда приходит O (n). Формула раскрывает идею, стоящую за ней: для n последовательных целых чисел сумма должна быть (n + 1) * n / 2. Если число отсутствует, сумма будет равна сумме (n + 1) последовательных целых чисел за вычетом пропущенного числа.

Спасибо, что указали на то, что я задумал кое-что среднее.

Молодцы Муравьи Аасма! Я думал над ответом около 15 минут и независимо придумал ответ в том же ключе, что и ваш:

#define SWAP(x,y) { numerictype_t tmp = x; x = y; y = tmp; }
int minNonNegativeNotInArr (numerictype_t * a, size_t n) {
    int m = n;
    for (int i = 0; i < m;) {
        if (a[i] >= m || a[i] < i || a[i] == a[a[i]]) {
            m--;
            SWAP (a[i], a[m]);
            continue;
        }
        if (a[i] > i) {
            SWAP (a[i], a[a[i]]);
            continue;
        }
        i++;
    }
    return m;
}

m представляет собой «текущий максимально возможный выход с учетом того, что я знаю о первых i входах, и ничего не предполагая о значениях до входа в m-1».

Это значение m будет возвращено, только если (a [i], ..., a [m-1]) является перестановкой значений (i, ..., m-1). Таким образом, если a [i]> = m или если a [i] <i или если a [i] == a [a [i]], мы знаем, что m - неправильный результат и должен быть по крайней мере на один элемент ниже. Таким образом, уменьшая m и меняя местами a [i] на a [m], мы можем выполнить рекурсию.

Если это не так, но a [i]> i, тогда, зная, что a [i]! = A [a [i]], мы знаем, что замена a [i] на [a [i]] увеличит количество элементов на их собственном месте.

В противном случае a [i] должен быть равен i, и в этом случае мы можем увеличить i, зная, что все значения до этого индекса включительно равны их индексу.

Доказательство того, что это не может войти в бесконечный цикл, оставлено читателю в качестве упражнения. :)

Dafny фрагмент из ответов показывает муравьев , почему алгоритм в месте может произойти сбой. requiresПредварительное условие описывает , что значения каждого элемента не должны выходить за пределы массива.

method AntsAasma(A: array<int>) returns (M: int)
  requires A != null && forall N :: 0 <= N < A.Length ==> 0 <= A[N] < A.Length;
  modifies A; 
{
  // Pass 1, move every value to the position of its value
  var N := A.Length;
  var cursor := 0;
  while (cursor < N)
  {
    var target := A[cursor];
    while (0 <= target < N && target != A[target])
    {
        var new_target := A[target];
        A[target] := target;
        target := new_target;
    }
    cursor := cursor + 1;
  }

  // Pass 2, find first location where the index doesn't match the value
  cursor := 0;
  while (cursor < N)
  {
    if (A[cursor] != cursor)
    {
      return cursor;
    }
    cursor := cursor + 1;
  }
  return N;
}

Вставьте код в валидатор с предложением и без него forall ..., чтобы увидеть ошибку проверки. Вторая ошибка является результатом того, что проверяющий не может установить условие завершения цикла Pass 1. Доказывать это остается тому, кто лучше разбирается в этом инструменте.

Вот ответ на Java, который не изменяет ввод и использует время O (N) и N бит плюс небольшие постоянные накладные расходы памяти (где N - размер списка):

int smallestMissingValue(List<Integer> values) {
    BitSet bitset = new BitSet(values.size() + 1);
    for (int i : values) {
        if (i >= 0 && i <= values.size()) {
            bitset.set(i);
        }
    }
    return bitset.nextClearBit(0);
}

def solution(A):

index = 0
target = []
A = [x for x in A if x >=0]

if len(A) ==0:
    return 1

maxi = max(A)
if maxi <= len(A):
    maxi = len(A)

target = ['X' for x in range(maxi+1)]
for number in A:
    target[number]= number

count = 1
while count < maxi+1:
    if target[count] == 'X':
        return count
    count +=1
return target[count-1] + 1

Получил 100% за решение выше.

1) Фильтр отрицательный и нулевой

2) Сортировать / отличать

3) Посещение массива

Сложность : O (N) или O (N * log (N))

используя Java8

public int solution(int[] A) {
            int result = 1;
    boolean found = false;
    A = Arrays.stream(A).filter(x -> x > 0).sorted().distinct().toArray();
    //System.out.println(Arrays.toString(A));
    for (int i = 0; i < A.length; i++) {
        result = i + 1;
        if (result != A[i]) {
            found = true;
            break;
        }
    }
    if (!found && result == A.length) {
        //result is larger than max element in array
        result++;
    }
    return result;
}

Unordered_set можно использовать для хранения всех положительных чисел, а затем мы можем выполнить итерацию от 1 до длины unordered_set и увидеть первое число, которое не встречается.

int firstMissingPositive(vector<int>& nums) {

    unordered_set<int> fre;
    // storing each positive number in a hash.
    for(int i = 0; i < nums.size(); i +=1)
    {
        if(nums[i] > 0)
            fre.insert(nums[i]);
     }

    int i = 1;
    // Iterating from 1 to size of the set and checking 
    // for the occurrence of 'i'

    for(auto it = fre.begin(); it != fre.end(); ++it)
    {
        if(fre.find(i) == fre.end())
            return i;
        i +=1;
    }

    return i;
}

Решение через базовый javascript

var a = [1, 3, 6, 4, 1, 2];

function findSmallest(a) {
var m = 0;
  for(i=1;i<=a.length;i++) {
    j=0;m=1;
    while(j < a.length) {
      if(i === a[j]) {
        m++;
      }
      j++;
    }
    if(m === 1) {
      return i;
    }
  }
}

console.log(findSmallest(a))

Надеюсь, это кому-то поможет.

С питоном это не самый эффективный, но правильный

#!/usr/bin/env python3
# -*- coding: UTF-8 -*-
import datetime

# write your code in Python 3.6

def solution(A):
    MIN = 0
    MAX = 1000000
    possible_results = range(MIN, MAX)

    for i in possible_results:
        next_value = (i + 1)
        if next_value not in A:
            return next_value
    return 1

test_case_0 = [2, 2, 2]
test_case_1 = [1, 3, 44, 55, 6, 0, 3, 8]
test_case_2 = [-1, -22]
test_case_3 = [x for x in range(-10000, 10000)]
test_case_4 = [x for x in range(0, 100)] + [x for x in range(102, 200)]
test_case_5 = [4, 5, 6]
print("---")
a = datetime.datetime.now()
print(solution(test_case_0))
print(solution(test_case_1))
print(solution(test_case_2))
print(solution(test_case_3))
print(solution(test_case_4))
print(solution(test_case_5))

def solution(A):
    A.sort()
    j = 1
    for i, elem in enumerate(A):
        if j < elem:
            break
        elif j == elem:
            j += 1
            continue
        else:
            continue
    return j

это может помочь:

0- A is [5, 3, 2, 7];
1- Define B With Length = A.Length;                            (O(1))
2- initialize B Cells With 1;                                  (O(n))
3- For Each Item In A:
        if (B.Length <= item) then B[Item] = -1                (O(n))
4- The answer is smallest index in B such that B[index] != -1  (O(n))