Click here to read more about algorithmic interviewing
Topic describes
This is the KTH largest element in the 703. Data stream on LeetCode, with difficulty Easy.
Design a class that finds the KTH largest element in the data stream. Notice it’s the KTH largest element, not the KTH different element.
Please implement KthLargest class:
KthLargest(int k, int[] nums) uses the integer k and the integer stream nums to initialize the object. Int add(int val) Returns the KTH largest element in the current data stream after inserting val into the data stream nums. Example:
Input: [" KthLargest ", "add", "add", "add", "add", "add"] [[3] [4, 5, 8, 2], [3], [5], [10], [9], [4]] output: KthLargest KthLargest = new KthLargest(3, [4, 5, 8, 2]); kthLargest.add(3); // return 4 kthLargest.add(5); // return 5 kthLargest.add(10); // return 5 kthLargest.add(9); // return 8 kthLargest.add(4); // return 8Copy the code
Tip:
1 <= k <= 10^4
0 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
-10^4 <= val <= 10^4
The add method is called up to 10^4 times
The problem data guarantees that there are at least K elements in the array when looking for the KTH largest element
Bubble Sorting solution (TLE)
Each time add is called, the number is loaded into the array, and then iterated k times to find Top K by looking for the maximum value k times.
class KthLargest {
int k;
List<Integer> list = new ArrayList<>(10009);
public KthLargest(int _k, int[] _nums) {
k = _k;
for (int i : _nums) list.add(i);
}
public int add(int val) {
list.add(val);
int cur = 0;
for (int i = 0; i < k; i++) {
int idx = findMax(cur, list.size() - 1);
swap(cur++, idx);
}
return list.get(cur - 1);
}
int findMax(int start, int end) {
int ans = 0, max = Integer.MIN_VALUE;
for (int i = start; i <= end; i++) {
int t = list.get(i);
if(t > max) { max = t; ans = i; }}return ans;
}
void swap(int a, int b) {
intc = list.get(a); list.set(a, list.get(b)); list.set(b, c); }}Copy the code
- O(nk)O(nk)O(nk)
- Space complexity: O(n)O(n)O(n)
Quick sort solution
The above solution is O(nk)O(nk)O(nk), and it will time out when K is very large.
We can use quickdrain instead of bubbling.
Change the complexity to O(nlogn)O(n\log{n})O(nlogn), it cannot be said that O(nlogn)O(n\log{n})O(nlogn) must be lower than O(nk)O(nk)O(nk) O(nk), But O (nlog n) O (n \ log {n}) O (nlogn) usually closer to O (n) O (n) O (n).
O(nlogn)O(n\log{n})O(nlogn) the efficiency of the solution is equal to an O(n)O(n)O(n) O(n)O(n) algorithm with constant 15 or less:
class KthLargest {
int k;
List<Integer> list = new ArrayList<>(10009);
public KthLargest(int _k, int[] _nums) {
k = _k;
for (int i : _nums) list.add(i);
}
public int add(int val) {
list.add(val);
Collections.sort(list);
returnlist.get(list.size() - k); }}Copy the code
- O(nlogn)O(n\log{n})O(nlogn)
- Space complexity: O(n)O(n)O(n)
Priority queue solution
Build a small root heap of capacity K using the priority queue.
Put the first K items in numS into the priority queue (the top of the heap element is the maximum number of the first K items).
Then add item by item to the priority queue:
-
The number of elements in the heap reaches K:
- Add items less than or equal to the top of the heap: Add items are ranked first
k
After the large element. Direct to ignore - Add items larger than the heaptop: pop the heaptop element, add items to the priority queue, adjust the heap
- Add items less than or equal to the top of the heap: Add items are ranked first
-
If the number of elements in the heap is less than K, the item is added to the priority queue
Return the top element of the heap (there must be k elements in the heap when the answer is returned) :
class KthLargest {
int k;
PriorityQueue<Integer> queue;
public KthLargest(int _k, int[] _nums) {
k = _k;
queue = new PriorityQueue<>(k, (a,b)->Integer.compare(a,b));
int n = _nums.length;
for (int i = 0; i < k && i < n; i++) queue.add(_nums[i]);
for (int i = k; i < n; i++) add(_nums[i]);
}
public int add(int val) {
intt = ! queue.isEmpty() ? queue.peek() : Integer.MIN_VALUE;if (val > t || queue.size() < k) {
if(! queue.isEmpty() && queue.size() >= k) queue.poll(); queue.add(val); }returnqueue.peek(); }}Copy the code
- Time complexity: In the worst case,
n
Each element in the heap triggers a heap adjustment. Complexity of
- Space complexity: O(k)O(k)O(k)
The last
This is the No.* of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics on LeetCode as of the start date, some of which have locks.
In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.
As the number of LeetCode questions keeps increasing with weekly and biweekly competitions, in order to facilitate our progress statistics, we will calculate the progress according to the total number of questions at the beginning of the series as the denominator and the completed questions as the numerator. Current progress is */1916.
In order to facilitate students to debug and submit codes on computers, I have set up a relevant warehouse on Github: github.com/SharingSour…
In the repository, you’ll see links to the series, the corresponding code for the series, the LeetCode source links, and some other preferred solutions.