https://leetcode.com/problems/kth-largest-element-in-a-stream
703. Kth Largest Element in a Stream
实作 KthLargest class
KthLargest(int k, int[] nums) 代表之后要找 nums 当中第 k 大的数
int add(int val) 可以使用 add 新增 val 到 nums 当中 并回传第 k 大的数字
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
Python Code:
class KthLargest:
def __init__(self, k: int, nums: List[int]):
self.k = k
nums.sort(reverse=True)
self.nums = nums[:k]
def add(self, val: int) -> int:
if len(self.nums) < self.k:
self.nums.append(val)
self.nums.sort(reverse=True)
elif val > self.nums[-1]:
self.nums.pop()
self.nums.append(val)
self.nums.sort(reverse=True)
return self.nums[-1]
之后问了 chatGPT 怎么找到 val 该放入 nums 的哪个位置
一开始给了 bisect 不过是用给升序排序的列表 所以改手做
Python Code:
class KthLargest:
def __init__(self, k: int, nums: List[int]):
self.k = k
nums.sort(reverse=True)
self.nums = nums[:k]
def find_insert_position_desc(self, k):
low, high = 0, len(self.nums)
while low < high:
mid = (low + high) // 2
if self.nums[mid] > k:
low = mid + 1
else:
high = mid
return low
def add(self, val: int) -> int:
if len(self.nums) < self.k:
self.nums.insert(self.find_insert_position_desc(val), val)
elif val > self.nums[-1]:
self.nums.pop()
self.nums.insert(self.find_insert_position_desc(val), val)
return self.nums[-1]
不会 heapq :(