※ 引述《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)