Улучшение временной сложности функции, которая возвращает индекс первого вхождения элемента в списке - PullRequest
Новая
       10

Улучшение временной сложности функции, которая возвращает индекс первого вхождения элемента в списке

0 голосов
/ 16 октября 2018

ОБНОВЛЕНИЕ 1 (16 октября) : в исходном коде было несколько логических ошибок, которые были исправлены.Обновленный код, приведенный ниже, теперь должен обеспечивать корректный вывод для всех списков L, ST, которые соответствуют критериям для специального списка.

Я пытаюсь уменьшить время выполнения следующей функции:

Функция "firstrepeat" принимает специальный список L и индекс и выдает наименьшееиндекс такой, что L [i] == L [j].Другими словами, каким бы ни был элемент в L [i], функция «firstrepeat» возвращает индекс первого появления этого элемента в списке.

Что особенного в списке L?:

  • Список может содержать повторяющиеся элементы в возрастающей или убывающей части списка.сторона, но не обе.то есть [3,2,1,1,1,5,6] хорошо, но не [4,3,2,2,1,2,3]

  • Список уменьшается (илиоставаясь прежним), а затем увеличиваясь (или оставаясь прежним).

  • Примеры: 

    L = [4,2,0,1,3] 
L = [3,3,3,1,0,7,8,9,9]
L = [4,3,3,1,1,1]
L = [1,1,1,1]

ПримерВывод:

Скажем, у нас L = [4,3,3,1,1,1]

firstrepeat (L, 2) выдаст 1

firstrepeat (L, 5) выдаст 3

У меня есть следующий код.Я считаю, что сложность O (log n) или лучше (хотя я мог что-то упустить).Я ищу способы улучшить сложность времени. 

def firstrepeat(L, i):
    left = 0
    right = i
    doubling = 1
    #A Doubling Search
    #In doubling search, we start at one index and then we look at one step 
    #forward, then two steps forward, then four steps, then 8, then 16, etc. 
    #Once we have gone too far, we do a binary search on the subset of the list 
    #between where we started and where we went to far.
    while True:
        if (right - doubling) < 0:
            left = 0
            break
        if L[i] != L[right - doubling]:
            left = right - doubling
            break
        if L[i] == L[right - doubling]:
            right = right - doubling
            doubling = doubling * 2
    #A generic Binary search
    while right - left > 1:
        median = (left + right) // 2
        if L[i] != L[median]:
            left = median
        else:
            right = median

    f L[left] == L[right]:
        return left
    else: 
        return right
...