求助：HackerRank频率查询代码的问题排查与性能优化

I've looked at your code and the problem you're facing—let's break down why those test cases are failing and how to fix the timeout issue for good.

First, Let's Diagnose the Problems #

Your initial code had two main issues:

• Incorrect deletion logic: The first version checked if value in res.keys() before decrementing, but if res[value] was already 0, this would still let you decrement it to -1. That messed up your frequency values and caused wrong answers in those 3 test cases. Your fix to check if res[value] > 0 resolved this, but there's still a critical performance bottleneck...
• O(n) query time for operation 3: Every time you run a type 3 query (3 z), checking value in res.values() forces Python to iterate through every single frequency in your counter. For large input sizes (like 100,000+ queries), this turns your solution into an O(n²) operation—way too slow, which is why you're hitting that timeout.

The Fix: Track Frequencies of Frequencies #

The key optimization here is to add a second counter that keeps track of how many numbers have a specific frequency. Let's call this freq_counts:

• num_counts: Maps each number to its current occurrence count (what you already have).
• freq_counts: Maps each frequency value to how many numbers have that frequency.

This way, checking if any number has a frequency of z (operation 3) becomes an O(1) lookup instead of O(n).

Optimized Code Walkthrough #

Here's the revised code with explanations for each step:

from collections import Counter

def freqQuery(queries):
    num_counts = Counter()
    freq_counts = Counter()
    output = []
    
    for op, value in queries:
        if op == 1:
            # Insert operation: increment count of 'value'
            old_freq = num_counts.get(value, 0)
            if old_freq > 0:
                freq_counts[old_freq] -= 1
                # Clean up zero entries to keep counters tidy (optional)
                if freq_counts[old_freq] == 0:
                    del freq_counts[old_freq]
            # Update the number's frequency
            num_counts[value] += 1
            new_freq = old_freq + 1
            freq_counts[new_freq] += 1
        
        elif op == 2:
            # Delete operation: decrement count of 'value' (only if it exists)
            old_freq = num_counts.get(value, 0)
            if old_freq == 0:
                # No instances to delete, skip
                continue
            # Remove the old frequency from freq_counts
            freq_counts[old_freq] -= 1
            if freq_counts[old_freq] == 0:
                del freq_counts[old_freq]
            # Update the number's frequency
            num_counts[value] -= 1
            new_freq = old_freq - 1
            if new_freq > 0:
                freq_counts[new_freq] += 1
            else:
                # If frequency hits 0, remove the number from num_counts
                del num_counts[value]
        
        elif op == 3:
            # Check if any number has frequency 'value'
            output.append(1 if freq_counts.get(value, 0) > 0 else 0)
    
    return output

Why This Works #

• Operation 1: When we increment a number's count, we first decrease the count of its old frequency in freq_counts, then increase the count of its new frequency.
• Operation 2: When we decrement a number's count, we do the reverse—adjust freq_counts for the old and new frequency, and clean up the number from num_counts if its frequency drops to 0.
• Operation 3: Instead of scanning all frequencies, we just check if freq_counts has a positive count for the target frequency—this is instant, even for huge datasets.

Testing With Your Example #

Let's run through your sample input queries = [[1, 1], [2, 2], [3, 2], [1, 2], [1, 1], [1, 1], [2, 1], [3, 2]]:

1. After [1,1]: num_counts={1:1}, freq_counts={1:1}
2. [2,2]: No 2 exists, skip.
3. [3,2]: freq_counts has no 2, append 0.
4. [1,2]: num_counts={1:1,2:1}, freq_counts={1:2}
5. [1,1]: num_counts={1:2,2:1}, freq_counts={1:1,2:1}
6. [1,1]: num_counts={1:3,2:1}, freq_counts={1:1,3:1}
7. [2,1]: num_counts={1:2,2:1}, freq_counts={1:1,2:1}
8. [3,2]: freq_counts has 2 with count 1, append 1.

Final output is [0,1] which matches the sample—perfect!

This solution will pass all test cases, including the large ones that were timing out before, since every operation runs in O(1) average time.

内容的提问来源于stack exchange，提问作者Rick K.