Найти минимальное натуральное число, отсутствующее в константном однонаправленном списке длинной N, за минимальное кол-во проходов списка. Использовать не более M дополнительной памяти.Питон только начинаю осваивать, подскажите пожалуйста как решить эту задачу, гугл почти не помог.
Показать необходимое максимальное кол-во проходов списка выраженное в О-нотации.
fmlolkan - количество элементов в списке
Что значит O(n^2)?
#!/usr/bin/env python # -*- coding: utf-8 -*- from random import randint class Node: """Описываем элемент связанного одностороннего списка. Параметры: value — значение элемента списка next — указатель на следующий элемент """ def __init__(self, value=None, next=None): self.value = value self.next = next def generator_link_lists(q, start, stop): """Генератор списка. Параметры: q — длина списка start — начальные значения генератора случайного натурального числа. stop — конечные значения генератора случайного натурального числа. """ yield (Node(value=randint(start, stop), next=i) for i in range (q)) def find_min_value(q, start, stop): """Возвращает минимальное натуральное число, не входящее в значения связанного списка. Если такового нет, то возвращает None """ link_lists = generator_link_lists(q, start, stop) # Инициализация генератора result = min(x.value for x in link_lists.next()) if result > 1: return result - 1 else: return None if __name__ == '__main__': print(find_min_value(100000, 100, 1000000))
AlenВы напрасно создаете случайный список, потому что если бы использовали, например (1, 3, 5) то сразу бы увидели, что требуемую 2 ваш код не выдает.
Сложность O(n)
AlenДля списка 1 2 3 4 5 должен выдать 6.return None
PooH
Вы напрасно создаете случайный список, потому что если бы использовали, например (1, 3, 5) то сразу бы увидели, что требуемую 2 ваш код не выдает.
py.user.next
Для списка 1 2 3 4 5 должен выдать 6.