Найти минимальный элемент, отсутствующий в последовательности неотрицательных целых чисел

Question

Мне нужно найти минимальный недостающий элемент из последовательности неотрицательных целых чисел.

Пример: у меня есть: 0 5 10 4 3 1

The missing element is 2.

В приведенной выше последовательности недостающими элементами являются 2 6 7 8 9. Минимум среди них 2, поэтому ответ 2.

Грубая сила. Я отсортирую последовательность и получу минимальный элемент в nlogn. Я ищу лучшее решение. Любая помощь?

Answer 1

В ISO C99:

unsigned least_absent(unsigned seq_sz, unsigned seq[seq_sz])
{
   bool tab[seq_sz];
   memset(tab, 0, sizeof(tab));
   for(unsigned i=0; i<seq_sz; i++)
      if(seq[i] < seq_sz)
         tab[seq[i]] = true;
   for(unsigned i=0; i<seq_sz; i++)
      if(!tab[i])
         return i;
   return seq_sz;
}

Это O (n) время, O (n) память.

Answer 2

Может быть выполнено в O (n) с помощью хеш-таблицы, что означает O (n) дополнительной памяти:

1. Вставьте числа в хеш-таблицу, выполненные в O (n).
2. Перейдите от нуля к максимуму списка и проверьте, существует ли число.Первое число, которое не существует, является ответом.Это также делается в O (n).

Answer 3

Это решение является O (n) пространственно-временной сложностью.

def solution(A):
    #Python 3.6

    a = set() #to store positive numbers in the given array
    b = set() #to store missing positive numbers in the given array

    for item in A:
        if item<=0:
            continue
        a.add(item)
        if item in b:
            b.remove(item)
        if item + 1 not in a:
            b.add(item+1)

    #if all numbers are negative in the given array
    if len(a) == 0:
        return 1

    #if 1 is not in the given array, 1 is the answer
    if 1 not in a:
        return 1

    return min(b)

Answer 4

list = sort(list)
last_element = list[0]
for(i = 1; i < list.size; ++i){
   if(list[i] - last_element > 1) 
      return last_element + 1 // return the next number after last_element
   last_element = list[i]
}
return -1 // return -1 if unable to find a number

Answer 5

Улучшение некоторых идей (@Faisal Feroz, @slacker, @dahunter, @ user453201): Во время передачи списка значений (сортировка или вставка значений в хэш-таблицу) сохраните минимум. Затем, чтобы найти недостающий элемент, начните с этого минимума вместо 0. Небольшое улучшение, но оно все же лучше.

Answer 6

Если вы знаете, что нет повторяющихся элементов, которые вы можете сделать за O (N log N) с помощью памяти O (1):

Вы выполняете двоичный поиск , чтобы найти ответ: изначально вы знаете, что ответ находится между 0 и N-1, для каждого шага вы подсчитываете, сколько чисел меньше k (k средний элемент сегмента двоичного поиска), если это число равно k, то эта частьпоследовательности завершена, поэтому вам нужно искать в верхней части, в противном случае вам нужно искать в нижней части.

Answer 7

Псевдокод:

a is the array
s is a sorted set (examples : a binary search tree, or a red/black tree)

insert 0 in s
for each v in a
  remove v from s
  insert v+1 in s

result is min(s)

Answer 8

Сначала отсортируйте элементы.Затем начните находить числа в вашей последовательности, например:

for (int i=0; i<numbers.length; i++) {
   if (numbers[i] != i ) {
       System.out.println("Missing number is: " + i); break;
   }
}

Answer 9

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

Я не уверен, что есть что-то намного проще.Даже если вы как-то проанализируете список, не отсортировав его, вам нужно будет отследить пробелы, которые вы обнаружили на этом пути, а затем устранить их по ходу работы.Я думаю, что это все равно логически эквивалентно алгоритму сортировки.Может быть не так.

Answer 10

1. Сортировка массива (O(NlogN) наихудший случай для сортировки слиянием)
2. Цикл с самого начала, пока не встретится разница более 1 между двумя соседними элементами.(O(N) наихудший случай)