Re: [閒聊] 每日leetcode
看板Marginalman作者sustainer123 (caster )時間1年前 (2024/08/12 09:09)推噓0(0推 0噓 2→)留言2則, 2人參與討論串697/1548 (看更多)
※ 引述《enmeitiryous (enmeitiryous)》之銘言：
: 等補完課下午再來寫昨天的
: 題目: 703. Kth Largest Element in a Stream
: 設計一個class每次回傳stream中第k大的element，一開始的kthlargest會給定k和起始一
: 個代表stream的vector，之後的add(val) func會將val加入倒stream中，並回傳stream中
: 第k大的數字
: 思路:
: 這題可以很直觀用暴力法，一開始先sort好stream，之後每次add則是用upper_bound找出
: val應該插在哪，插完後回傳第k大的數，但結果很爛，正確的解法應該是要保持一個k大
: 小的min heap根據val值判斷要直接回傳heap top還是pop後push val再回傳，注意的是
: constraint是保證insert完能找到第k大，所以insert前當前heap可能為空
: priority_queue<int, vector<int>, greater<int> > pre_ans;
: int gg=0;
: KthLargest(int k, vector<int>& nums) {
: gg=k;
: for(auto pp:nums){
: if(pre_ans.size()<k){
: pre_ans.push(pp);
: }
: else{
: if(pp>pre_ans.top()){
: pre_ans.pop();
: pre_ans.push(pp);
: }
: }
: }
: }
: int add(int val) {
: if(pre_ans.size()<gg){
: pre_ans.push(val);
: return pre_ans.top();
: }
: if(val<=pre_ans.top()){
: return pre_ans.top();
: }
: else{
: pre_ans.pop();
: pre_ans.push(val);
: return pre_ans.top();
: }
: }
思路1:
暴力解
Python Code:
class KthLargest:
def __init__(self, k: int, nums: List[int]):
self.k = k
self.nums = nums
def add(self, val: int) -> int:
self.nums.append(val)
self.nums.sort()
return self.nums[-(self.k)]
# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)
思路2:
heap
Python Code:
class KthLargest:
def __init__(self, k: int, nums: List[int]):
self.k = k
self.heap = nums
heapq.heapify(self.heap)
while len(self.heap) > k:
heapq.heappop(self.heap)
def add(self, val: int) -> int:
if len(self.heap) < self.k or val > self.heap[0]:
heapq.heappush(self.heap,val)
if len(self.heap) > self.k:
heapq.heappop(self.heap)
return self.heap[0]
# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.194.160.111 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1723424998.A.0C5.html
→
08/12 10:47,
1年前
, 1F
08/12 10:47, 1F
→
08/12 11:05,
1年前
, 2F
08/12 11:05, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 697 之 1548 篇)：