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

Ответ 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

Ответ 2

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

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

На практике "массив из N booleans", вероятно, будет закодирован как "битмап" или "битсет", представленный как массив 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 являются разновидностью сортировки counting. В некотором смысле он прав, но различия значительны:

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

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

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

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

Ответ 3

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

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

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

Ответ 4

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

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

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

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

Ответ 5

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

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

Ответ 6

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

Ответ 7

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

1. установить U = N; L=0 U = N; L=0
2. Сначала разделите пространство номеров на k регионов. Как это:
   • 0->(1/k)*(UL) + L, 0->(2/k)*(UL) + L, 0->(3/k)*(UL) + L... 0->(UL) + 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} U = count{h}; L = count{h-1}
7. перейти к 2

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

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

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

Ответ 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

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

Ответ 9

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

Ответ 10

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

Ответ 11

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

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

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

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

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

Ответ 12

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

Ответ 13

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

Ответ 14

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

            }
        }

Ответ 15

Здесь мой ответ написан на Java:

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

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

3 Найдите разницу между суммами, вычисленными на этапах 1 и 2

4- Повторите цикл от 1 до минимума [разности сумм, max] и верните первое число, которое не находится в карте, заполненной на шаге 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;
}

Ответ 16

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

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

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

Ответ 17

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

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

Ответ 18

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

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)

Ответ 19

Молодцы Ants 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 представляет "текущий максимальный возможный выход, учитывая то, что я знаю о первых входах я и не предполагаю ничего больше о значениях до ввода в m-1".

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

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

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

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

Ответ 20

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

Ответ 21

Здесь ответ на 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);
}

Ответ 22

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

Ответ 23

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

Ответ 24

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

Ответ 25

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

Ответ 26

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

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

Ответ 27

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

Ответ 28

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

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