Hackerrank 频率查询

Question

您将得到一些查询。每个查询都有以下两个整数形式：

1.将x插入数据结构中。 2.如果存在，则从数据结构中删除y的一个实例。 3.检查是否存在任何出现频率正好为y的整数。如果是，则打印1，否则打印0。

示例输入：

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

问题相当明显，我认为我有一个不错的解决方案：

循环遍历查询，并根据需要增加和减少每个数字的频率在字典中 ......同时，在另一个字典中跟踪其他字典键出现的次数

对于查询3的检查，如果存在频率恰好为y的任何整数，则应检查第二个字典中y的计数是否存在...

我通过了大部分测试用例，但是有些测试用例失败了...有人可以解释我的思路有什么缺陷吗？

def freqQuery(queries):
    frequency = {}
    results = []
    frequencyValues = {}
    for query in queries:
        q = query[0]
        val = query[1]
        if q == 1:
            frequency[val] = frequency.get(val, 0) + 1
            freq = frequency[val]
            frequencyValues[freq] = frequencyValues.get(freq, 0) + 1
            frequencyValues[freq-1] = frequencyValues.get(freq-1, 1) - 1
        elif q == 2:
            if val in frequency.keys():
                frequency[val] += - 1
                if frequency[val] < 0:
                    frequency[val] = 0
                freq = frequency[val]
                frequencyValues[freq + 1] = frequencyValues.get(freq + 1, 1) - 1
                frequencyValues[freq] = frequencyValues.get(freq, 1) + 1
        elif q == 3:
            if val in frequencyValues.keys():
                if frequencyValues[val] > 0:
                    results.append(1)
                else:
                    results.append(0)
            else:
                results.append(0)
            

    return results

- user1990406

Answer 1

# --stackoverflow help fixing op code

# minor code refactor and your code passes all the test cases.

    elif q == 2:
        if val in frequency:

            freq = frequency[val]
            frequencyValues[freq] = frequencyValues.get(freq, 1) - 1

            frequency[val] += - 1 # <---- decrement line
            frequencyValues[freq-1] = frequencyValues.get(freq-1, 1) + 1

            #-------------------- 
            if frequency[val] < 0:
                frequency[val] = 0
            #--------------------

            # this condition should have been checked at the end as after decrement line ( frequency[val] -= 1 ) value of frequency[val] can get negative

            # also frequency[val] += - 1 ---> can be better written as frequency[val] -= 1

我的解决方案已通过全部测试用例

from collections import defaultdict
n = int(input())

a = defaultdict(int) # num:cnt
b = defaultdict(int) # cnt: how many nums have this cnt

for tc in range(n):
    op, data = map(int, input().strip().split())

    if op == 1:
        # insert
        b[a[data]] -= 1
        a[data]+=1
        b[a[data]] += 1

    elif op == 2:
        # delete
        if data in a:
            b[a[data]] -= 1
            a[data] -= 1
            b[a[data]] += 1

        a[data]  = 0 if a[data] < 0 else a[data]

    else:
        # check if any key in b = data and has count > 0         
        print('1' if data in b and b[data] > 0  else '0')

第一种方法，但在4个测试用例中遇到了超时问题。

from collections import defaultdict
n = int(input())

data_freq_dict = defaultdict(int)

for tc in range(n):
    op, data = map(int, input().strip().split())

    if op == 1:
        # insert
        data_freq_dict[data]+=1

    elif op == 2:
        # delete
        if data in data_freq_dict:
            data_freq_dict[data] -= 1

        data_freq_dict[data]  = 0 if data_freq_dict[data] < 0 else data_freq_dict[data]

    else:
        # check if any key in data_freq_dict has count = data         
        print('1' if data in set(data_freq_dict.values()) else '0')

- Tanmay jain

---

非常感谢 - 我知道那个字典有问题，但我无法找到任何合理大小的测试用例来确定原因。 - user1990406

Answer 2

def freqQuery(queries):
    arr={}
    res=[]
    for i,j in queries:
        if i==1:
            if j in arr:
                arr[j]+=1
            else:
                arr[j]=1
        elif i==2:
            if j in arr:
                if arr[j]>0:
                    arr[j]-=1
        elif i==3:
            if j in arr.values():
                res.append(1)
            else:
                res.append(0)
    return res

由于超时，Python3编译器只有一个测试用例会失败。因此，我在pypy3中运行它，因为它比Python3编译得更快...

注意：这里只使用了一个字典。我认为在最优解中会使用两个字典。

- Nikhil Manu