1

Что поправить в коде, чтобы он проходил по времени за 2 секунды:

N = 5
elements = [1, 1, 2, 2, 2] # Список с элементами
request = [1, 2, 3] # Список с запросами
def search(elements, request):
    array = elements[::-1]
    for element in request:
        try : temp = elements.index(element)   
        except ValueError: print('-1 -1')
        if element in elements:
            print(temp+1, N - array.index(element))

search(elements, request)

1 < N < 100000 Необходимо для каждого запроса, найти номер первого и последнего вхождения в список elements, если элемент не найден, то вывести '-1 -1'

3
  • Судя по условию задачи, здесь работа для find/rfind
    – strawdog
    Commented 22 окт. 2019 в 18:25
  • А список не сортированный ли?
    – MBo
    Commented 22 окт. 2019 в 18:33
  • @MBo, список упорядоченный в порядке неубывания
    – link_brt
    Commented 22 окт. 2019 в 19:23

3 ответа 3

3

Раз список упорядочен, то гораздо быстрее будет использовать бинарный поиск - он сработает за логарифмическое время.

Подойдут bisect_left и bisect_right из модуля bisect

import bisect
N = 5
elements = [1, 1, 3, 3, 3, 5, 5] # Список с элементами
request = [0, 1, 2, 3, 6] # Список с запросами
def search(elements, request):
    for element in request:
        l = bisect.bisect_left(elements, element)
        r = bisect.bisect_right(elements, element)
        if r == l or l >= len(elements) or r <= 0:
            print(element, -1, -1)
        else:
            print(element, l, r - 1)

search(elements, request)

0 -1 -1
1 0 1
2 -1 -1
3 2 4
6 -1 -1

P.S. Если запросов не больше, чем элементов, то выгоднее отсортировать запросы, а затем просто пройти по списку элементов по порядку - сортированные запросы гарантируют, что назад возвращаться не придется, и второй этап будет линейным.

1
  • валит все тот же третий тест. Закрадывается подозрение, что ошибка на стороне серва, а не у меня. Пойду спрошу у препода
    – link_brt
    Commented 23 окт. 2019 в 19:34
1

Если числа исключительно однозначные натуральные (0-9), то можно попробовать сделать так:

elements = [1, 1, 2, 2, 2] # Список с элементами
request = [1, 2, 3] # Список с запросами

mystr=''.join([str(x) for x in elements])
for i in request:        
    print(f"request: {i} -> first entry: {mystr.find(str(i))}, last entry: {mystr.rfind(str(i))}")

получим:

request: 1 -> first entry: 0, last entry: 1
request: 2 -> first entry: 2, last entry: 4
request: 3 -> first entry: -1, last entry: -1

UPDATE

Если же в исходном списке вообще сборная солянка, то можно сделать так:

elements = [1, 1, 2, 20.5, 2, 'boo', 5] # Список с элементами
request = [1, 2, 20.5, 3, 'boo', 6] # Список с запросами

res = [print(x,':',elements.index(x), len(elements) - 1- elements[::-1].index(x)) if x in elements else print(x,':', -1, -1) for x in request]

получим:

1 : 0 1
2 : 2 4
20.5 : 3 3
3 : -1 -1
boo : 5 5
6 : -1 -1
6
  • Числа не только натуральные :(
    – link_brt
    Commented 22 окт. 2019 в 19:22
  • @link_brt обновил ответ. теперь осталось протестировать на скорость.
    – strawdog
    Commented 22 окт. 2019 в 20:21
  • в исходном списке находятся числа, упорядоченные в порядке неубывания. Сейчас проверим на скорость
    – link_brt
    Commented 22 окт. 2019 в 20:41
  • валит все на том же тесте
    – link_brt
    Commented 22 окт. 2019 в 20:57
  • @link_brt Раз массив упорядоченный, то, скорей всего, нужно будет использовать, бинарный поиск или что-то в этом роде.
    – Joker
    Commented 22 окт. 2019 в 21:30
0

Попытался по подсказкам из комментариев реализовать двоичный поиск, получается с этими входными данными:

elements = [1, 1, 2, 2, 2]
request = [1, 2, 3]
def BinSearchLeft(array, key):
    l = -1
    r = len(array)
    while l < r - 1:
        m = (l + r) // 2
        if array[m] < key:
            l = m
        else: r = m
    return r + 1

def BinSearchRight(array, key):
    l = -1
    r = len(array)
    while l < r - 1:
        m = (l + r) // 2
        if array[m] <= key:
            l = m
        else: r = m
    return r

with open('binsearch.out', 'w') as file:
    for element in request:
        if element in elements:
            print(BinSearchLeft(elements, element),BinSearchRight(elements,element), file=file)
        else: print(-1, -1, file=file)

Но почему то выдает ошибку с другими входными данными, где я допустил ошибку?

1
  • Посмотрите мой пример
    – MBo
    Commented 23 окт. 2019 в 18:15

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.