Ваш ответ на вопрос

Комментарии

meow Апрель 10, 2020 в 19:51

# Есть два списка одинакового размера. # В каждом содержатся одинаковые отсортированные элементы, но во втором, # начиная с какого-то элемента, этот порядок меняется. # Найти индекс элемента, начиная с которого списки начинают отличаться. # Сложность алгоритма - log(n) # Вначале поймем, что именно от нас хотят и прикинем, какой результат # должны давать различные входы, смотри ассерты ниже. # !!! И только после этого начинаем писать код. from typing import List def func(a: List, b: List) -> int: if len(a) != len(b): return -1 start = 0 end = len(a) - 1 while start < end: mid = (end + start) // 2 if a[mid] == b[mid]: # до mid порядок не нарушается, значит нужно проверять # в правой половине start = mid + 1 else: # порядок нарушился до mid, значит нужно проверять # в левой половине end = mid # в конце останется срез из одного элемента start == end # в качестве результата возвращаем одно из этих значений # не забывая при этом проверить, что end не равен границе # исходных списков - в этом случае порядок не нарушался if end == len(a) - 1: return -1 return start assert(func([1], [1]) == -1) assert(func([1, 2], [2, 1]) == 0) assert(func([], []) == -1) assert(func([1, 2, 3], [1, 2, 3]) == -1) assert(func([1, 2, 3], [1, 2]) == -1) assert(func([1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 6, 5]) == 4)

Stureiko Igor Февраль 17, 2020 в 14:43

Деление пополам даст искомую сложность