Интересный вопрос для поиска: найдите значение, которого НЕТ в списке (Daily coding problem, 26 мая 2020 г.) - PullRequest
Новая
       5

Интересный вопрос для поиска: найдите значение, которого НЕТ в списке (Daily coding problem, 26 мая 2020 г.)

0 голосов
/ 27 мая 2020

Мне было интересно, не захочет ли кто-нибудь дать мне отзыв о моем решении сегодняшнего вопроса из списка рассылки Daily Coding. Это интересный вопрос о поиске первого значения, которое НЕ присутствует в списке, в отличие от поиска значения, которое там ЕСТЬ.

Эта проблема была задана Stripe.

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

Например, вход [3, 4, -1, 1] должен давать 2. Вход [1, 2, 0] должен давать 3.

Вы можете изменить входной массив на месте.

Мой главный вопрос в том, что я не уверен, соблюдал ли я требования времени O (n) и пространства O (1). Вот мое решение с использованием Groovy: 

def find_first( Xs ) {
  ys = []
  szXs = Xs.size()
  // First, transfer Xs list to a set ys.
  szXs.times { // this loop is O(n)
    if ( (hd = Xs.head()) > 0 ) { ys << hd; } // We only need to keep val if it's positive.
    Xs = Xs.drop(1); // Remove val from Xs in order to meet O(1) space requirement.
  }
  ys = ys.toSet() // converting list to set is O(n)
  sz = ys.size()  // ys.size() might be same as Xs.size(), but it could be smaller, so give it a new var.
  for (int i = 1; i < sz; ++i) { // this loop is O(n)
    if ( !ys.contains(i) ) return i // Testing a hash set for set membership is O(1)
  }
  return sz + 1 // if this point is reached, ys had all values [1..sz] already
} // end find_first

def test(Xs) {
  println "\nstarting with Xs = " + Xs
  ans1 = find_first( Xs )
  println "first missing = " + ans1
}

xs1 = [ 3,4,-1,1 ]
xs2 = [ 1, 2, 0 ]
xs3 = [ 7, 8 ]
xs4 = [ 1,1,2,1 ]
xs5 = [ -4, -1 ]

test(xs1)
test(xs2)
test(xs3)
test(xs4)

test (xs5)

И вот результат:

, начиная с Xs = [3, 4, - 1, 1] первый пропущенный = 2

начиная с Xs = [1, 2, 0] первый пропущенный = 3

начиная с Xs = [7, 8] первый пропущенный = 1

начиная с Xs = [1, 1, 2, 1] сначала отсутствует = 3

начиная с Xs = [-4, -1] сначала отсутствует = 1

Так что это правильно для этого ограниченного набора значений, просто хочу быть уверенным, что это время O (n) и пространство O (1). Любой совет приветствуется! Хэнк

1 Ответ

0 голосов
/ 29 мая 2020

Я не знаком с groovy, но похоже, что ваш код - это O(n) пробел, поскольку вы создаете дополнительный ha sh set (ys).

Обратите внимание, что вопрос имеет подсказку:

Вы можете изменить входной массив на месте.

Это можно сделать за O(n) время с пробелом O (1), сначала сортировка массива на месте с помощью radix sort , а затем перебор значений для поиска первого отсутствующего.

...