121. Top K Frequent Numbers in a Stream
Top K Frequent Numbers in a Stream
Implement a class that supports the following operations on numbers:
insert(num) - insert a number into the data structure.
isTopK(num) - return whether the number is currently among the top k most frequent numbers in the data structure.
The frequency of a number is the number of times it has been inserted so far.
The ranking must be determined by:
1. Higher frequency comes first.
2. If two numbers have the same frequency, the smaller number comes first.
A number is considered in the top k if it appears within the first k positions of this ranking.
If fewer than k distinct numbers have been inserted, every inserted distinct number is considered part of the top k.
If a number has never been inserted, isTopK(num) must return false.
Class
TopKFrequentNumbers
Methods
TopKFrequentNumbers(int k)
- Initializes the data structure with the given
k.
1 ≤ k ≤ 10^5
void insert(int num)
- Inserts
num into the data structure and updates its frequency.
-10^9 ≤ num ≤ 10^9
boolean isTopK(int num)
- Returns
true if num is currently among the top k most frequent numbers; otherwise returns false.
-10^9 ≤ num ≤ 10^9
Ranking Rules
- Numbers are ranked by decreasing frequency.
- If frequencies are equal, the smaller number gets the better rank.
- Only distinct numbers are ranked.
Constraints
1 ≤ k ≤ 10^5-10^9 ≤ num ≤ 10^9- At most
10^5 total calls will be made to insert and isTopK.
isTopK(num) does not change the data structure.
Examples
Example 1
TopKFrequentNumbers tracker = new TopKFrequentNumbers(k = 2)
tracker.insert(num = 5)
tracker.isTopK(num = 5)
Output: true
Explanation: Only one distinct number has been inserted: 5 with frequency 1. Since fewer than 2 distinct numbers exist, 5 is in the top 2.
Example 2
TopKFrequentNumbers tracker = new TopKFrequentNumbers(k = 2)
tracker.insert(num = 5)
tracker.insert(num = 7)
tracker.insert(num = 7)
tracker.isTopK(num = 7)
Output: true
Explanation: The frequencies are:
7 -> 2
5 -> 1
The ranking is [7, 5], so 7 is in the top 2.
Example 3
TopKFrequentNumbers tracker = new TopKFrequentNumbers(k = 2)
tracker.insert(num = 5)
tracker.insert(num = 7)
tracker.insert(num = 7)
tracker.insert(num = 3)
tracker.insert(num = 3)
tracker.isTopK(num = 5)
Output: false
Explanation: The frequencies are:
3 -> 2
7 -> 2
5 -> 1
Since 3 and 7 have the highest frequencies, the top 2 numbers are [3, 7]. Therefore, 5 is not in the top 2.
Example 4
TopKFrequentNumbers tracker = new TopKFrequentNumbers(k = 2)
tracker.insert(num = 10)
tracker.insert(num = 20)
tracker.isTopK(num = 20)
Output: true
Explanation: Both 10 and 20 have frequency 1. Because frequencies are equal, the smaller number comes first, so the ranking is [10, 20]. Since 20 is still within the first 2 positions, it is in the top 2.
Example 5
TopKFrequentNumbers tracker = new TopKFrequentNumbers(k = 3)
tracker.insert(num = 4)
tracker.insert(num = 4)
tracker.insert(num = 8)
tracker.isTopK(num = 6)
Output: false
Explanation: The number 6 has never been inserted, so isTopK(6) returns false.