Помогите ускорить программу. Мутанты

Question

Мутанты

Уже долгое время в Институте Искусств, Мутантов и Информационных Технологий разводят милых разноцветных зверюшек. Для удобства каждый цвет обозначен своим номером, всего цветов не более 10**9. В один из прекрасных дней в питомнике случилось чудо: все зверюшки выстроились в ряд в порядке возрастания цветов. Пользуясь случаем, лаборанты решили посчитать, сколько зверюшек каждого из запрошенных цветов живет в питомнике, и, по закону жанра, попросили вас написать программу, которая поможет им в решении этой нелегкой задачи.

Входные данные

В первой строке входных данных содержится единственное число N (0≤N≤10^5) — количество зверюшек в Институте. В следующей строке находятся N упорядоченных по неубыванию неотрицательных целых чисел, не превосходящих 10^9 и разделенных пробелами — их цвета. В третьей строке записано число M (1≤M≤100000) — количество запросов вашей программе, в следующей строке через пробел записаны M целых неотрицательных чисел (не превышающих 10^9+1).

Выходные данные

Выведите M строчек: для каждого запроса в отдельной строке выведите число зверюшек заданного цвета в питомнике.

Примеры Ввод

10
1 1 3 3 5 7 9 18 18 57
5
57 3 9 1 179

Вывод

Недавно начал изучать Питон, вот мое решение:

def C(d,b):
    l=0
    for i in range(len(d)):
        for j in range(len(b)):
            if d[i]==b[j]:
                l+=1
        print(l)
        l=0
       
a=int(input())
b=input().split()
c=int(input())
d=input().split()  
g=C(d,b)

Выдает, что программа выполнялась слишком долго. Второй вариант программы. Выполняется неверно для примера, но если вбить другие данные, то все правильно:

a=int(input())
b= list(map(int, input().split()))
c=int(input())
d= list(map(int, input().split()))
d=sorted(d)
for i in range(c):
        print(b.count(d[i]))

Answer 1

Ваше решение имеет асимптотическую сложность O(N * M) (делает около 10^10 операций, когда питон успевает порядка 10^6 в секунду), потому что при ответе на каждый запрос в худшем случае вы перебираете все элементы изначального массива (count тоже проходит по всем элементам).

Я вижу два основных способа решить эту задачу "быстро" (за O(M*log(N))): с использованием словаря, либо извращенный с использованием бинарного поиска.

Со словарем (кстати, он будет работать даже если массив A неотсортированный):

n = int(input())
a = [int(i) for i in input().split()]

count = {}
if n > 0:
    count[a[0]] = 1
    for i in range(1, n):
        if a[i] == a[i - 1]:
            count[a[i]] += 1
        else:
            count[a[i]] = 1

m = int(input())
b = [int(i) for i in input().split()]
for q in b:
    if q in count:
        print(count[q])
    else:
        print(0)

Алгоритм с бинарным поиском не слишком удобный, но идея такая: необходимо найти самое левое и самое правое вхождение X в массив, после чего вычислить количество элементов в данном отрезке. Поскольку реализация получится не очень красивая, то код пишите сами (реально напишите, вам умение написания бинарного поиска пригодится).

Сейчас еще придумал третий способ со сложностью O(M*log(M) + N), в котором нужно отсортировать массив запросов:

n = int(input())
a = [int(i) for i in input().split()]
m = int(input())
b = [int(i) for i in input().split()]

c = [[b[i], i] for i in range(m)]
c.sort()
ans = [0] * m

u = 0
for i in range(n):
    while u < m and a[i] > c[u][0]:
        u += 1
    if u == m:
        break

    if a[i] == c[u][0]:
        ans[c[u][1]] += 1

for i in ans:
    print(i)

Answer 2

раз уж начали выкладывать код, то попробуйте этот. любопытно, уложится по времени или нет.

def C(a,b,c,d):
    result=[0]*c
    for i in range(a):
        if b[i] in d:
            g=d.index(b[i])
            result[g]+=1
    for i in result:
        print(i)


a=int(input())
b=input().split()
c=int(input())
d=input().split()
g=C(a,b,c,d)

Answer 3

Для того чтобы использовать Бин. поиск есть библиотека в Пайтон называется bisect, в ней есть методы bisect_left и bisect_right которые как раз и находят первое и последнее вхождение элемента соответственно. (Работает быстро)

Вот код:

from bisect import bisect_left, bisect_right


n = int(input())
a = list(map(int, input().split()))
m = int(input())
b = list(map(int, input().split()))

for i in b:
    print(bisect_right(a, i) - bisect_left(a, i))

БЛОГ НА HUSL

Помогите ускорить программу. Мутанты

Мутанты

Ответы (3 шт):