Учитывая неупорядоченный список целых чисел, верните значение, не указанное в списке

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

У меня есть список из N элементов целых чисел, которые могут содержать элементы 1-M (M > N), далее список не сортируется. Я хочу функцию, которая будет принимать этот список в качестве входных данных и возвращать значение в диапазоне 1-M, отсутствующее в списке. Список не содержит дубликатов. Я надеялся на решение o (N), не используя дополнительное пространство UPDATE: функция не может изменить исходный список L

например, N = 5 M = 10 Список (L): 1, 2, 4, 8, 3  то f (L) = 5 Честно говоря, я не забочусь о том, возвращает ли он элемент, отличный от 5, только если он встречает вышеприведенные ограничения

Единственное решение, с которым я столкнулся, заключается в использовании дополнительного массива из M элементов. Прохождение списка входных данных и установка соответствующих элементов массива в 1, если они присутствуют в списке. Затем снова итерируем этот список и возвращаем индекс первого элемента со значением 0. Как вы видите, это использует дополнительное пространство o (M) и имеет сложность 2 * o (N). Любая помощь была бы оценена нами.

Спасибо за помощь всем. Сообщество, безусловно, очень полезно. Чтобы дать каждому немного больше контекста проблемы, которую я пытаюсь решить. У меня есть набор маркеров M, которые я выдаю некоторым клиентам (по одному на каждого клиента). Когда клиент сделан с токеном, он возвращается в мою кучу. Поскольку вы можете видеть исходный заказ, который я даю клиенту, томек сортируется. так что M = 3     Tokens client1:1         < 2,3> client2: 2             < 3> client1 return: 1 < 1,3> клиент 3: 3     < 1> Теперь вопрос заключается в том, чтобы указать токен client4 1. Я мог на этом этапе предоставить клиенту 4 токена 2 и отсортировать список. Не уверен, что это поможет. В любом случае, если я придумаю хорошее чистое решение, я обязательно отправлю его Просто понял, что я мог смутить всех. У меня нет списка свободного токена со мной, когда меня зовут. Я мог бы статически поддерживать такой список, но я бы предпочел не

4 ответа

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

Если M велико по сравнению с N, скажем M > 2N, сгенерируйте случайное число в 1..M и проверьте, нет ли он в списке в O (N) времени, O (1). Вероятность того, что вы найдете решение за один проход, составляет не менее 1/2, и поэтому (геометрическое распределение) ожидаемое количество проходов является постоянным, средняя сложность O (N).

Если M является N + 1 или N + 2, используйте описанный ниже .


Вы можете разделить и победить. В основном, учитывая диапазон 1..m, используйте стиль быстрой сортировки с m/2 в качестве точки опоры. Если в первом тайме меньше, чем m/2, то есть недостающее число и итеративно его найти. В противном случае во втором тайме есть недостающее число. Сложность: n + n/2 + n/4... = O (n)

def findmissing(x, startIndex, endIndex, minVal, maxVal):
 pivot = (minVal+maxVal)/2
 i=startIndex
 j=endIndex
 while(True):
 while( (x[i] <= pivot) and (i<j) ):="" i+="1" if="" i="">=j:
 break
 while( (x[j] > pivot) and (i<j) ):="" j+="1" if="" i="">=j:
 break
 swap(x,i,j)
 k = findlocation(x,pivot)
 if (k-startIndex) < (pivot-minVal):
 findmissing(x,startIndex, k, minVal, pivot)
 else:
 findmissing(x, k+1, endIndex, pivot+1, maxVal)
</j)></j)>

Я не реализовал конечное условие, которое я оставлю вам.


После прочтения обновленного, я думаю, вы делаете его сложным. Прежде всего позвольте мне перечислить то, что я получаю от вашего вопроса.

  • Вам нужно предоставить токен клиенту независимо от его заказа, цитируя его с вашего оригинального сообщения.

например N = 5 M = 10 Список (L): 1, 2, 4, 8, 3, тогда f (L) = 5 To be честный я не забочусь, если он возвращает элемент, отличный от 5, так долго поскольку он соответствует вышеприведенным ограничениям

  • Во-вторых, вы уже просматриваете список токенов "M"
  • Клиент извлекает токен и после его использования возвращает его обратно

Учитывая эти 2 пункта, почему бы вам не реализовать TokenPool?

  • Реализовать свой список M на основе Очередь
  • Всякий раз, когда клиент запрашивает токен, извлекает токен из очереди, то есть удаляет его из очереди. Посредством этого метода ваша очередь всегда будет поддерживать те токены, которые не выдаются. вы делаете это O (1)
  • Всякий раз, когда клиент делается с токеном, он возвращает его обратно вам. Добавьте его обратно в очередь. Опять O (1).

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


Можете ли вы сделать что-то вроде сортировки? Создайте массив размера (M-1), затем перейдите в список один раз (N) и измените элемент массива, индексированный в i-1, на один. После однократного циклирования через N найдите 0 → (M-1), пока не найдете первый массив с нулевым значением.

Должен ли я O (N + M).

Массив L размера (M-1): [0 = 0, 1 = 0, 2 = 0, 3 = 0, 4 = 0, 5 = 0, 6 = 0, 7 = 0, 8 = 0, 9 = 0]

После петли через N элементов: [0 = 1, 1 = 1, 2 = 1, 3 = 1, 4 = 0, 5 = 0, 6 = 0, 7 = 1, 8 = 0, 9 = 0]

Поиск массива 0 → (M-1) находит, что индекс 4 равен нулю, поэтому 5 (4 + 1) - это первое целое число, не принадлежащее L.

licensed under cc by-sa 3.0 with attribution.