Есть два списка одинакового размера

Рома Июнь 5, 2020 в 20:37

meow, а если условие a[mid] == b[mid] выполнится случайно, несмотря на то, что порядок поменялся раньше?

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

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

Есть два списка одинакового размера

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

Комментарии