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

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

1. найти длину списка; допустим, это N.
2. выделите массив N логические значения, инициализированные для всех false.
3. для каждого номера X в списке, если X меньше N, установить X'th элемент массива true.
4. сканировать массив, начиная с index 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 биты в худшем и лучшем случаях.

---

EDIT: я изменил описание алгоритма, чтобы использовать "массив булевых значений", так как люди, по-видимому, нашли мое исходное описание с использованием битов и растровых изображений, чтобы запутать.

поскольку 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, где вы устраняете разделы, которые не являются потенциальными кандидатами для содержания зазора.

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

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

Так как все числа имеют длину 64 бита, мы можем использовать radix sort на них, что является 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"

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

1. set 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. set U = count{h}; L = count{h-1}
7. Гото 2

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

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 H-это ваш ответ
6. set U = maximum value in region hL = 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

Я сомневаюсь, что вы могли бы улучшить 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), даже если оно было бы намного быстрее.

спасибо Эгону, свилдену и Стивену Си за мое вдохновение. Во-первых, мы знаем границы значения цели, потому что оно не может быть больше размера списка. Кроме того, список 1GB может содержать не более 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;
}

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

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

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

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) n/2

EDIT: извините, я думаю, что думал слишком быстро прошлой ночью. Во всяком случае, вторая часть должна быть фактически заменена суммой(списком), где o(n) приходит. Формула раскрывает идея: для n последовательных целых чисел, сумма должна быть (Н+1)*н/2. Если есть пропущенное число, сумма будет равна сумма (n+1) последовательных целых чисел минус пропущенное число.

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

молодцы муравьи Aasma! Я думал над ответом около 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, ..., М-1). Таким образом, если a[i] >= m или если a [i]

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

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

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

The дафний фрагмент из ответа Муравьев показывает, почему алгоритм на месте может потерпеть неудачу. Элемент 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) Sort / distinct

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

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

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

надеюсь, что это поможет для кого-то.