Форум сайта python.su
Добрый день. Необходимо выполнить следующую задачу
Найти минимальное натуральное число, отсутствующее в константном однонаправленном списке длинной N, за минимальное кол-во проходов списка. Использовать не более M дополнительной памяти.Питон только начинаю осваивать, подскажите пожалуйста как решить эту задачу, гугл почти не помог.
Показать необходимое максимальное кол-во проходов списка выраженное в О-нотации.
Офлайн
O(n^2)
Начиная с единицы нужно просматривать весь список. Если единицы нет, то ответ - единица, иначе перейти к двойке и повторить. Повторять до тех пор, пока не дойдёшь до N + 1.
Отредактировано py.user.next (Фев. 1, 2015 01:00:25)
Офлайн
Что значит O(n^2)?
Офлайн
fmlolkan - количество элементов в списке
Что значит O(n^2)?
Офлайн
Сложность O(n)
#!/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.
Офлайн