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