文章作者：Tyan
博客：noahsnail.com | CSDN | 简书
1. Description
Kth Largest Element in a Stream
2. Solution
- Version 1
class KthLargest {
public:
KthLargest(int k, vector<int> nums) {
this->k = k;
sort(nums.begin(), nums.end());
this->nums = nums;
}
int add(int val) {
int pos = binarySearch(val);
nums.insert(nums.begin() + pos, val);
return nums[nums.size() - k];
}
private:
int k;
vector<int> nums;
int binarySearch(int val) {
int left = 0;
int right = nums.size() - 1;
while(left <= right) {
int mid = (left + right) / 2;
if(nums[mid] == val) {
return mid;
}
else if(nums[mid] > val) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
return left;
}
};
/**
* Your KthLargest object will be instantiated and called as such:
* KthLargest obj = new KthLargest(k, nums);
* int param_1 = obj.add(val);
*/
- Version 2
class KthLargest {
public:
KthLargest(int k, vector<int> nums) {
this->k = k;
sort(nums.begin(), nums.end(), greater<int>());
if(nums.size() > k) {
nums.resize(k);
}
this->nums = nums;
}
int add(int val) {
if(nums.size() == 0) {
nums.push_back(val);
return nums[k - 1];
}
if(val <= nums[k - 1] && nums.size() == k) {
return nums[k - 1];
}
int pos = binarySearch(val);
nums.insert(nums.begin() + pos, val);
if(nums.size() > k) {
nums.pop_back();
}
return nums[k - 1];
}
private:
int k;
vector<int> nums;
int binarySearch(int val) {
int left = 0;
int right = nums.size() - 1;
while(left <= right) {
int mid = (left + right) / 2;
if(nums[mid] == val) {
return mid;
}
else if(nums[mid] < val) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
return left;
}
};
/**
* Your KthLargest object will be instantiated and called as such:
* KthLargest obj = new KthLargest(k, nums);
* int param_1 = obj.add(val);
*/
- Version 3
class KthLargest {
public:
KthLargest(int k, vector<int> nums) {
this->k = k;
for(int i = 0; i < nums.size(); i++) {
pq.push(nums[i]);
if(pq.size() > k) {
pq.pop();
}
}
}
int add(int val) {
pq.push(val);
if(pq.size() > k) {
pq.pop();
}
return pq.top();
}
private:
int k;
priority_queue<int, vector<int>, greater<int> > pq;
};
/**
* Your KthLargest object will be instantiated and called as such:
* KthLargest obj = new KthLargest(k, nums);
* int param_1 = obj.add(val);
*/
