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

Question

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

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

ПОСЛЕДУЮЩАЯ ИНФОРМАЦИЯ: Теперь, когда было предложено очевидное решение с помощью сортировки, можете ли вы сделать это быстрее, чем O(n log n)?

ПОСЛЕДУЮЩАЯ ИНФОРМАЦИЯ: Ваш алгоритм должен работать на компьютере, скажем, с 1 ГБ памяти

ПОЯСНЕНИЕ: список находится в оперативной памяти, хотя он может потреблять большое количество. Вам задан размер списка, скажем N, заранее.

Answer 1

Если структура данных может быть изменена на месте и поддерживает произвольный доступ, то вы можете сделать это за O(N) времени и O(1) дополнительного пространства. Просто последовательно проходите массив и для каждого индекса записывайте значение в индексе в индекс, заданный значением, рекурсивно помещая любое значение в этом месте на свое место и выбрасывая значения> 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

Answer 2

Вот простой 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 биты в худшем и лучшем случаях.

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

---

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

Answer 3

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

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

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

Answer 4

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

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

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

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

Answer 5

Чтобы проиллюстрировать одну из ловушек 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"

Answer 6

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

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

Answer 7

Для метода, эффективного с точки зрения пространства, и все значения различны, вы можете сделать это в пространстве 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. перейти к 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 hL = minimum value in region h

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

Answer 8

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

С точки зрения алгоритма, что-то вроде этого сделало бы это:

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")

Answer 9

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

Answer 10

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

Answer 11

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

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

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

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

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

Answer 12

 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 !!");

            }
        }

Answer 13

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

Answer 14

Вы можете сделать это за 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), даже если оно будет намного быстрее.

Answer 15

Вот мой ответ, написанный на 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;
}

Answer 16

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;
}

Answer 17

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% за вышеуказанное решение.

Answer 18

Я не уверен, что получил вопрос. Но если для списка 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) последовательных целых чисел минус пропущенное число.

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

Answer 19

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

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))

Answer 20

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

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).

Answer 21

Решение с помощью основного 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))

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

Answer 22

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

#!/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))

Answer 23

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

Answer 24

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

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

Answer 25

Вот ответ в 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);
}

Answer 26

Молодцы Муравьи Аасма! Я думал об ответе около 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]

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

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

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

Answer 27

Набор 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;
}

Answer 28

Фрагмент Дафни из ответа Антса показывает, почему алгоритм на месте может дать сбой. 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. Доказательство этого оставлено тому, кто лучше разбирается в инструменте.