→ JerryChungYC: 話說到底有沒有leetcode群ㄚ 一直忘了問 08/12 13:07
推 sustainer123: 你找二跑 他群主 08/12 13:08
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 :(
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.251.52.67 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1723439128.A.8CA.html