Блог

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

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

 The missing element is 2.
  

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

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

В 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) памяти.

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

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

 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
  

Это решение имеет 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)
  

Псевдокод:

 for(int i = 0 ; i < Int.MAX ; i  )
{
   if(i is not in list)
   {
       return i
    }
}
  

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

Нет необходимости в сортировке.

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

2. Выведите (было найдено наименьшее значение) 1.

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

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

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

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

Псевдокод :

 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)
  

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

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

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

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