Разбор задач
Кондратий решил поднять научный и культурный уровень знаний жителей Трешландии. Для этого он стал собирать разную полезную информацию.
Начал Кондратий с науки. Он захотел составить рейтинг авторов научных публикаций. Специально для этого придумали индекс «замечаемости».
Индекс «замечаемости» автора равен
k, если из всех
n его работ на
k ссылаются минимум
k раз другие авторы, а остальные
n−k работ имеют не более
k ссылок
Например, у гамбургеролога (учёный в Трешландии, который исследует влияние количества потребления гамбургеров населением на количество бездомных собак) Гришки Гречкина 5 работ. Количество ссылок на каждую из них: [3, 0, 4, 1, 5].
Индекс «замечаемости» Гришки равен 3, ведь он написал 3 работы, на которые другие учёные сослались минимум 3 раза. А на остальные его работы ссылались менее 3 раз.
Ребятам поручили написать функцию, которая по списку c количеством цитат для каждой из работ автора определяет его индекс «замечаемости». Если возможных ответов несколько, нужно вернуть максимальный из них.
Гоша: Как будем решать задачу?
Рита: Кажется, нужно отсортировать массив. Заведём переменную notice_index, которая будет означать индекс «замечаемости». Инициализируем её нулем. Далее будем идти по массиву с конца и смотреть: если текущий элемент больше notice_index, увеличим значение notice_index на 1. В конце вернём полученное значение.
Скопировать кодPYTHON
def noticeIndex(arr):
arr.sort()
notice_index = 0
for i in range(len(arr) - 1, -1, -1):
if arr[i] > notice_index:
notice_index += 1
return notice_index
Рассмотрим на примере с Гришкой Гречкиным.
На вход подаётся массив arr = [3, 0, 4, 1, 5].
Отсортируем его и получим такой массив: [0, 1, 3, 4, 5].
На первом шаге цикла текущий элемент равен 5, а значение notice_index — 0.
Увеличим значение notice_index на 1.
На следующем шаге текущий элемент — 4. Это значение снова больше notice_index, которое равно уже 1. Добавим ещё 1 к значению notice_index.
На третьем шаге элемент равен 3. Снова увеличим notice_index на 1. Его значение будет уже 3.
На четвертом шаге элемент равен 1. Это значение меньше notice_index, поэтому изменений не будет. На последнем шаге тоже. Вернём из функции 3.
Тимофей: Да, хороший алгоритм. Но его можно оптимизировать. Если текущее значение в массиве не больше notice_index, можно выйти из цикла. Ведь массив отсортирован, значит обновлений больше не будет. Так мы избежим лишних операций сравнения.
К тому же, можно сразу отсортировать массив по невозрастанию. Такой код проще читать.
Получим такую функцию:
Скопировать кодPYTHON
def noticeIndex(arr):
arr.sort(reverse = True)
notice_index = 0
for i in range(len(arr)):
if arr[i] > notice_index:
notice_index += 1
else:
break
return notice_index
Гоша: Отлично! Мне вообще понравилась тема про сортировки. Столько разных методов для одной задачи. Давайте порешаем ещё что-нибудь?
Тимофей: Давайте. Будем сортировать список.
Рита: Ну сколько можно тебе говорить, не список, а массив. Массив — название абстрактной структуры данных. Не все же на Python пишут. Я вот, например, в основном, писала на C++, пока у вас не начала работать.
Тимофей: Всё-таки мы будем сортировать список. Связный список.
Гоша: Ха! Бонд. Джеймс Бонд.
Алла: Без Джеймса Бонда как-нибудь справимся. Я вот знаю как, это простая задача. Составим из списка массив, отсортируем его и преобразуем в связный список.
Тимофей: Есть ограничения. Сложность по времени должна быть
O(nlogn).
Гоша: Вообще-то решение Аллы подходит.
Тимофей: Есть ещё одно ограничение. Сложность по памяти —
O(1).
Рита: Нужно написать сортировку, которая работает за
O(nlogn), похожую на сортировку массива.
Тимофей: Верно, будем реализовывать алгоритм сортировки слиянием для связного списка.
Например, для списка -2 → 1 → 0 → -5 → 10 → 4 функция должна вернуть -5 → -2 → 0 → 1 → 4 → 10.
Класс, задающий узел связного списка:
Скопировать кодPYTHON
class ListNode(object):
def __init__(self, val, next=None):
self.val = val
self.next = next
def __repr__(self):
return str(self.val)
Основная функция принимает на вход голову списка. Назовём функцию sortList.
Скопировать кодPYTHON
def sortList(head):
if not head:
return None
length = 1
node = head
tail = None
while node.next:
node = node.next
length += 1
tail = node
return merge_sort(head, tail, length)
В функции sortList определим длину списка и его хвост. С этими параметрами вызовем функцию merge_sort(head, tail, length).
В этой рекурсивной функции реализована сортировка слиянием.
Базовый случай рекурсии — head и tail совпадают либо tail — это head.next.
В первом случае список состоит из одного элемента. Установим ему в качестве next None. Мы так делаем, потому что алгоритм подразумевает переупорядочивание элементов в списке. Возможно, значение head.next меньше, чем у head. Это нам не подходит. После обновления значения вернём head из функции.
Во втором случае список состоит из двух элементов. Вернём из функции меньший из элементов, а в поле next у него будет больший из элементов.
Перейдём к рекурсивному случаю.
Определим средний элемент. По нему разобьём список на две части и рекурсивно вызовем merge_sort для обеих частей.
Возвращать будем результат функции merge. Эта функция сливает два отсортированных списка.
Скопировать кодPYTHON
def merge_sort(head, tail, length):
if head == tail:
head.next = None
return head
if head.next == tail:
if head.val < tail.val:
tail.next = None
return head
head.next, tail.next = None, head
return tail
i = 1
node = head
while i < length / 2:
node = node.next
i += 1
length1 = length2 = length / 2
if length % 2:
length2 += 1
tail1, head2 = node, node.next
left_part = merge_sort(head, tail1, length1)
right_part = merge_sort(head2, tail, length2)
return merge(left_part, right_part)
Рассмотрим функцию слияния. На вход она принимает головы двух списков. Каждый из них отсортирован.
Алгоритм похож на алгоритм слияния двух отсортированных массивов.
Скопировать кодPYTHON
def merge(head1, head2):
if head1.val < head2.val:
cur, tmp, other = head1, head1.next, head2
else:
cur, tmp, other = head2, head2.next, head1
mergedList = cur
if not tmp:
cur.next = other
return mergedList
while tmp:
if tmp.val < other.val:
cur, tmp = tmp, tmp.next
else:
t = tmp
cur.next = other
cur = other
other = t
tmp = cur.next
cur.next = other
return mergedList
Соединим все функции вместе.
Скопировать кодPYTHON
def sortList(head):
if not head:
return None
length = 1
node = head
tail = None
while node.next:
node = node.next
length += 1
tail = node
return merge_sort(head, tail, length)
def merge_sort(head, tail, length):
if head == tail:
head.next = None
return head
if head.next == tail:
if head.val < tail.val:
tail.next = None
return head
head.next, tail.next = None, head
return tail
i = 1
node = head
while i < length / 2:
node = node.next
i += 1
length1 = length2 = length / 2
if length % 2:
length2 += 1
tail1, head2 = node, node.next
left_part = merge_sort(head, tail1, length1)
right_part = merge_sort(head2, tail, length2)
return merge(left_part, right_part)
def merge(head1, head2):
if head1.val < head2.val:
cur, tmp, other = head1, head1.next, head2
else:
cur, tmp, other = head2, head2.next, head1
mergedList = cur
if not tmp:
cur.next = other
return mergedList
while tmp:
if tmp.val < other.val:
cur, tmp = tmp, tmp.next
else:
cur.next = other
cur = other
other = tmp
tmp = cur.next
cur.next = other
return mergedList
Гоша: Здорово получилось! Но всё-таки сортировка слиянием для массива мне понятнее.
Тимофей: На самом деле суть алгоритма такая же. Отличия лишь в реализации.
Гоша: Действительно? Сложность тоже получается
O(nlogn)? Что-то не верится.
Тимофей: Сложность именно такая. Всего делений логарифм. На каждом шаге мы разбиваем и соединяем список. Сложность соединения для списков такая же, как в случае с массивом —
O(n). В разбиении есть отличие. Массив можно разбить пополам за
O(1). В случае связного списка требуется
O(n) операций.
То есть всего
O(logn) шагов, на каждом из которых сложность
O(n). Общая сложность сортировки слиянием для связного списка
O(nlogn).