Может ли кто-нибудь помочь разобраться в проблеме в моем коде запросов частоты хакерского ранга?

Question

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

queries = [[1, 1], [2, 2], [3, 2], [1, 2], [1, 1], [1, 1], [2, 1], [3, 2]]

Каждый запрос имеет форму,

1 x -> insert x

2 y -> удалить одно вхождение y

3 z -> Проверить, присутствует ли какое-либо целое число, частота которого точно равна z. Если да, напечатайте 1 else 0

Например,

Operation   Array   Output
(1,1)       [1]
(2,2)       [1]
(3,2)                   0
(1,1)       [1,1]
(1,1)       [1,1,1]
(2,1)       [1,1]
(3,2)                   1

В приведенном выше примере возвращается массив с выводом: [0, 1]

Мое решение:

def freqQuery(queries):
    res = Counter()
    output = []

    for op, value in queries:
        if op == 1:
            res[value] += 1
        elif op == 2:
            if value in res.keys():
                res[value] -= 1
        elif op == 3:
            if value in res.values():
                output.append(1)
            else:
                output.append(0)

    return output

Ссылка на проблему: https://www.hackerrank.com/challenges/frequency-queries/problem

Тесты 4/15 не проходят с 3 неправильными ответами и одним с превышением лимита времени. Может кто подскажет, что не так с кодом?

Обновление:

Спасибо за помощь! Мой второй запрос был неверным.

Новое решение:

def freqQuery(queries):
    res = Counter()
    output = []

    for op, value in queries:
        if op == 1:
            res[value] += 1
        elif op == 2:
            if res[value] > 0:
                res[value] -= 1
        elif op == 3:
            if value in res.values():
                output.append(1)
            else:
                output.append(0)

    return output

Хотя я все еще не проваливаю один тестовый пример, т.е. превышаю лимит времени. Что я мог сделать, чтобы повысить эффективность кода?

Answer 1

Неправильный ответ очевиден. Вы не поняли запрос 3. В запросе 3 вас спросят, есть ли какой-либо ключ, счетчик которого в словаре равен z.

        elif op == 2:
            if value in res.keys():
                res[value] -= 1

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

Вы не удаляете какие-либо ключи из Counter.

Подумайте о простом случае, вас попросят добавить 2 your_code_state: ({2:1}), затем удалите 2 дважды your_code_state: {2:-1}, затем добавьте 2 еще раз your_code_state: {2:0}, проверьте, существует ли какой-либо z = 1, для вашего кода нет your_code_state: {2:0} (поскольку вы продолжаете уменьшать свой счетчик, даже если он отрицательный), но ответ должен быть 1 {2:1}.

Итак, просто проверьте, отрицательный ли счетчик, если да, не уменьшайте, оставайтесь на 0.

Для улучшения времени не повторяйте in проверок, вы можете сохранить отдельный словарь / ha sh map, в котором будет храниться частота для каждого подсчета, например, если есть частота z, второй dict будет содержать dict2[z] = 1, иначе 0. Это принесет вниз все ваши операции в функции запроса до O (1).

# Complete the freqQuery function below.
from collections import Counter
def freqQuery(queries):
    d = Counter() # actual values and their count
    f = Counter() # keep the frequency, if f[z] > 0, then we return 1
    output = []
    for command, key in queries:
        if command == 1:
            d[key] += 1 # new value add
            f[d[key]] += 1 # new frequency add
            f[d[key]-1] -= 1 # delete old frequency
        elif command == 2:
            if d[key] > 0:
                d[key] -= 1 # delete
                f[d[key]] += 1 # old frequency increase
                f[d[key]+1] -= 1
        else:
            if f[key] > 0: # O(1)
                output.append(1)
            else:
                output.append(0)
    return output