702717. Top k numbers in a stream
Top k numbers in a stream
Slug: top-k-numbers3425
Difficulty: Medium
Id: 702717
Topic Tags: Arrays, Map, priority-queue, Data Structures
Company Tags: Accolite, Amazon, Media.net
Summary
Given a continuous stream of integers, find the top k numbers in descending order. This problem involves using data structures such as arrays and maps to efficiently keep track of the highest k numbers seen so far.
Detailed Explanation
To solve this problem, we can use a combination of an array and a priority queue (min-heap). The idea is to maintain a min-heap of size k which stores the top k numbers. As new numbers are streamed in, we can easily update the heap by removing the smallest number if the new number is larger, or inserting the new number into the heap.
Here's a step-by-step breakdown of the solution:
- Initialize an array to store the numbers and a min-heap of size k.
- Iterate over the stream of numbers:
- For each number, check if the heap has less than k elements. If yes, simply insert the new number into the heap.
- If the heap already has k elements, compare the new number with the smallest element in the heap (which is the root of the min-heap). If the new number is larger, remove the smallest element from the heap and insert the new number.
- After processing all numbers, return the top k numbers in descending order by extracting them from the heap.
The time complexity for this solution is O(n log k), where n is the total number of elements in the stream. This is because we are performing a constant amount of work for each element and using a min-heap to keep track of the top k elements, which takes O(log k) time per operation. The space complexity is O(k), as we need to store the top k elements in the heap.
Optimized Solutions
Java
import java.util.*;
class Solution {
public int[] getTopKNumbers(int[] numbers, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
List<Integer> result = new ArrayList<>();
for (int num : numbers) {
if (minHeap.size() < k) {
minHeap.add(num);
} else {
if (num > minHeap.peek()) {
minHeap.poll();
minHeap.add(num);
}
}
}
while (!minHeap.isEmpty()) {
result.add(minHeap.poll());
}
int[] topKNumbers = new int[k];
for (int i = k - 1; i >= 0; i--) {
topKNumbers[i] = result.get(i);
}
return topKNumbers;
}
}