Попытка найти первый отсутствующий положительный результат с помощью переменной in-loop

Question

Учитывая список целых чисел, я хочу найти первый пропущенный положительный.Моя идея состояла в том, чтобы сделать это, используя переменную внутри цикла for, чтобы избежать беспорядка.Вот что я сделал:

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        sort_list = sorted(nums)
        holder = 0
        item = 1

        for item in range(len(sort_list)):

            if sort_list[item] != item:
                holder = item

        return holder

Так вот, что я сделал.Сначала я отсортировал список по возрастанию.Затем я инициализировал 2 переменные holder = 0 и item = 1.Поскольку данный список должен начинаться с 1, я также попытался запустить цикл for с 1.Причина в том, что если бы мне дали список типа [7, 8, 9, 5, 5, 3], первым пропущенным положительным должен быть один.В любом случае, затем я попытался перебрать каждый элемент в списке, чтобы увидеть, сравнивается ли он item, а если нет, я присвоил holder = item и возвратил holder.Однако, в конечном итоге он вернул 0, когда мой ввод был [1, 2, 0], когда он должен был вернуть 3.

Answer 1

Добавьте все числа в набор, затем последовательно проверьте 1, 2, 3 и т. Д., Чтобы увидеть, есть ли они в наборе:

def first_missing_positive(number_list):
    number_set = set(number_list)
    for n in range(1, len(number_list) + 1):
        if n not in number_set:
            return n
    return None

print(first_missing_positive([7, 6, 5, 3, 2, 1, 8]))

Отпечатки:

4

Другой подход:

Все числа 1, 2, ... len (список ввода) добавляются в набор.Затем числа в переданном списке удаляются из этого набора, и возвращается наименьшее число в оставшемся наборе.Это может быть улучшением по сравнению с первым решением, особенно когда первое отсутствующее положительное число находится ближе к концу (высокое положительное значение), поскольку цикл в Python может быть медленнее, чем вычисления набора, выполненные в его реализации на языке Си.

def first_missing_positive(number_list):
    return  min(set(range(1, len(number_list) + 1)) - set(number_list))

Answer 2

Вы можете попробовать set:

def missingPos(x):
    y = set(range(1,max(x)+2))
    return min(y-set(x))

print(missingPos([7, 8, 9, 5, 5, 3]))
print(missingPos([1,2,0]))

Вывод:

1
3

Лучшим решением было бы использование итераторов, которые будут эффективны в памяти для расчетов с большими списками:

def missingPos(x):
    generator = (i for i in range(1,max(x)+2) if i not in x)
    print(next(generator))
missingPos([1,2,0])
missingPos([7, 8, 9, 5, 5, 3])

Выход:

3
1

Answer 3

Ваша проблема в том, что вы даете holder значение (0) в начале, поэтому, если вы не найдете пропущенное значение, оно вернет 0. Это решит вашу проблему:

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        sort_list = sorted(nums)
        holder = None

        for item in range(len(sort_list)):

            if sort_list[item] != item:
                holder = item

        return holder if holder is not None else item+1

Answer 4

Это немного упрощено, хотя, если входные данные являются большими списками, вы должны игнорировать этот ответ

from operator import eq
def firstMissingPositive(nums):
    l = list(map(eq, nums, range(1, len(nums)+1)))
    return l.index(False) + 1 if False in l else -1

Answer 5

Я попробовал это немного по-другому:

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        max = len(nums)

        for i in range(1,max+2):
            if i not in nums:
                return i

Вы можете просто проверить, есть ли текущий номер из итерации в списке, его не нужно сортировать.

*Диапазон 1005 * составляет от 1 до макс. + 2, потому что если вы получили список типа [1,2,3,4], он должен считать от 1 до 5, чтобы найти 5 как пропущенное число.