703. Kth Largest Element in a Stream (Easy)
https://leetcode.com/problems/kth-largest-element-in-a-stream/
Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.
Your KthLargest
class will have a constructor which accepts an integer k
and an integer array nums
, which contains initial elements from the stream. For each call to the method KthLargest.add
, return the element representing the kth largest element in the stream.
Example:
int k = 3; int[] arr = [4,5,8,2]; KthLargest kthLargest = new KthLargest(3, arr); kthLargest.add(3); // returns 4 kthLargest.add(5); // returns 5 kthLargest.add(10); // returns 5 kthLargest.add(9); // returns 8 kthLargest.add(4); // returns 8
Note:
You may assume that nums
' length ≥ k-1
and k
≥ 1.
Solutions
1.
class KthLargest {
private int k;
private Queue<Integer> pq = new PriorityQueue<>();
public KthLargest(int k, int[] nums) {
this.k = k;
for (int num : nums) {
add(num);
}
}
public int add(int val) {
pq.offer(val);
// drop all that after the kth element
if (pq.size() > k) {
pq.poll();
}
return pq.peek();
}
}
2.
class KthLargest {
// This solution is too trivial and you will make mistakes.
// The preferred choice is to use array or list instead of linked list.
// It's easy to come across setback due to the complexity of linked list.
// It is strongly advised to make a draft before get down to coding, or the
// bugs will drive you crazy.
class Node {
int val = 0;
Node prev = null;
Node next = null;
public Node(int val) {
this.val = val;
}
}
int k = 0;
int size = 0;
Node head = null;
Node kthNode = null;
public KthLargest(int k, int[] nums) {
this.k = k;
head = new Node(Integer.MAX_VALUE);
kthNode = head;
for (int i = 0; i < nums.length; i++) {
add(nums[i]);
}
}
public int add(int val) {
Node newP = new Node(val);
int count = 1;
Node pointer = head;
while(pointer.next != null) {
if (pointer.next.val < val) {
break;
}
count++;
pointer = pointer.next;
}
if (pointer.next != null) {
pointer.next.prev = newP;
}
newP.next = pointer.next;
newP.prev = pointer;
pointer.next = newP;
size++;
// If the length of list is not as long as k, move kthNode forward
if (size <= k && kthNode.next != null) {
kthNode = kthNode.next;
}
// If the insert slot is in front of or just in kth position, move
// back the pointer of kthNode
// Be aware that only list length > k, you can move back.
if (size > k && count <= k) {
kthNode = kthNode.prev;
}
return kthNode.val;
}
}