99클럽 코테 스터디 10일차 TIL - Kth Largest Element in a Stream

---

Kth Largest Element in a Stream

출처 : LeetCode

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.

Implement KthLargest class:

• KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of integers nums.
• int add(int val) Appends the integer val to the stream and returns the element representing the kth largest element in the stream.

Example 1:

• Input
  ["KthLargest", "add", "add", "add", "add", "add"]
  [[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
• Output
  [null, 4, 5, 5, 8, 8]

Explanation

• 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 8

Constraints:

• 1 <= k <= 104
• 0 <= nums.length <= 104
• -104 <= nums[i] <= 104
• -104 <= val <= 104
• At most 104 calls will be made to add.
• It is guaranteed that there will be at least k elements in the array when you search for the kth element.

---

/**
 * @param {number} k
 * @param {number[]} nums
 */
 // 클래스 구현
var KthLargest = function(k, nums) {
    // k: 3, nums: [4, 5, 8, 2]
    this.k = k;
    this.nums = nums.sort((a, b) => b - a);
};

/** 
 * @param {number} val
 * @return {number}
 */
KthLargest.prototype.add = function(val) {
    // nums 배열에 정수 val을 추가함.
    // nums 배열에서 k번째로 큰 수를 반환함.
    // 4, 5, 8, 2, 3 -(내림차순 정렬)-> 8, 5, 4, 3, 2
    // 이때 3번째로 큰 요소(k번째로 큰 값)인 4를 반환함.
    this.nums.push(val);
    this.nums.sort((a, b) => b - a);
    return this.nums[this.k - 1];
};

/** 
 * Your KthLargest object will be instantiated and called as such:
 * var obj = new KthLargest(k, nums)
 * var param_1 = obj.add(val)
 */