注意multiset的一个bug：
multiset带一个参数的erase函数原型有两种。一是传递一个元素值，如上面例子代码中，这时候删除的是集合中所有值等于输入值的元素，并且返回删除的元素个数；另外一种是传递一个指向某个元素的iterator，这时候删除的就是这个对应的元素，无返回值。
https://www.cnblogs.com/lakeone/p/5600494.html
删除的时候一定不能删除指针，只能删除迭代器
leetcode那个题就是在这个地方出错的：
Expected: 2
如果container.erase(*con)，最后小根堆的大小就只有19个
container.erase(con)才是正确的
剑指offer 最小的k个数：
这是partition版本的
class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
vector<int> result;
int length = input.size();
if(input.empty() || length <= || k <= || length < k)
return result;
int start = ;
int end = length - ;
int index = partition(input,start,end);
while(index != k-){
if(index > k-){
end = index - ;
index = partition(input,start,end);
}
else{
start = index + ;
index = partition(input,start,end);
}
}
for(int i = ;i < k;i++)
result.push_back(input[i]);
return result;
}
int partition(vector<int> &input,int start,int end){
int small = start - ;
for(int i = start;i < end;i++){
if(input[i] < input[end]){
small++;
if(small != i)
swap(input,small,i);
}
}
small++;
swap(input,small,end);
return small;
}
void swap(vector<int>& input,int a,int b){
int tmp = input[a];
input[a] = input[b];
input[b] = tmp;
}
};
这是基于大根堆的：
class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
vector<int> output;
int length = input.size();
if(input.empty() || k <= || length < k)
return output;
multiset<int,greater<int>> numbers;
multiset<int,greater<int>>::iterator greaternumber;
vector<int>::iterator iter = input.begin();
for(;iter != input.end();iter++){
if(numbers.size() < k)
numbers.insert(*iter);
else{
greaternumber = numbers.begin();
if(*greaternumber > *iter){
numbers.erase(*greaternumber);
numbers.insert(*iter);
}
}
}
for(greaternumber = numbers.begin();greaternumber != numbers.end();greaternumber++){
output.push_back(*greaternumber);
}
return output;
}
};
leetcode 215. Kth Largest Element in an Array
使用小根堆
错误写法：
在这个情况：{3,2,3,1,2,4,5,5,6,7,7,8,2,3,1,1,1,10,11,5,6,2,4,7,8,5,6}，会报错
错误在container.erase(*con)，正确应该是container.erase(con)。erase(*con)删除的是数值，比如top是3，会把container里面所有的3都删除掉 ，erase(con)删除的是指针，只删除top的这个值
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
multiset<int,less<int>> container;
multiset<int,less<int>>::iterator con;
for(int i = ;i < nums.size();i++){
if(container.size() < k)
container.insert(nums[i]);
else{
con = container.begin();
if(*con < nums[i]){
container.erase(*con);
container.insert(nums[i]);
}
}
}
con = container.begin();
return *con;
}
};
正确写法：
可以写
if(length <= 0 || k <= 0 || length < k)
return -1;
针对这个判断条件，有可能输入的不全是正数，返回-1就有问题，原题目中其实是排除了这些边界条件的
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
multiset<int,less<int>> container;
multiset<int,less<int>>::iterator con;
//if(length <= 0 || k <= 0 || length < k)
//return -1;
for(int i = ;i < nums.size();i++){
if(container.size() < k)
container.insert(nums[i]);
else{
con = container.begin();
if(*con < nums[i]){
container.erase(con);
container.insert(nums[i]);
}
}
}
con = container.begin();
return *con;
}
};
使用partition的方式：
注意这里要增加end = index - 1和start = index + 1，因为这里不是递归，是使用的循环。如果你直接把end换成index - 1带入patition函数，对于之后的partition函数，这个end实际上还是没变的。
没有真正达到所以1/2的目的。
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int n = nums.size();
k = n - k;
int start = ,end = nums.size() - ;
int index = partition(nums,start,end);
int freq = ;
while(index != k){
if(index > k){
end = index - ;
index = partition(nums,start,end);
}
else{
start = index + ;
index = partition(nums,start,end);
}
}
return nums[index];
}
int partition(vector<int>& nums,int start,int end){
int index = start - ;
for(int i = start;i < end;i++){
if(nums[i] < nums[end]){
index++;
if(index != i)
swap(nums[index],nums[i]);
}
}
index++;
swap(nums[index],nums[end]);
return index;
}
};
80. Median
这个题是在无序数组中找经过排序后的中间位置的值。实际上这个题和Kth Largest Element in an Array差不多，Kth Largest Element in an Array是求第k大，这个题是限定了k是中间位置，并且要求时间复杂度是O(n)，所以使用partition的方式就可以。
时间复杂度分析：
https://rcoh.me/posts/linear-time-median-finding/
这是平局时间复杂度
实际上就是O(N) + O(N/2) + O(N/4) + O(N/8)....,使用等比数列求和公式：
就可以得到是一个O(2N)的复杂度，即O(N)
class Solution {
public:
/**
* @param nums: A list of integers
* @return: An integer denotes the middle number of the array
*/
int median(vector<int> &nums) {
// write your code here
int start = ,end = nums.size() - ;
int index = partition(nums,start,end);
int k = (nums.size() - )/;
while(k != index){
if(index < k){
start = index + ;
index = partition(nums,start,end);
}
else{
end = index - ;
index = partition(nums,start,end);
}
}
return nums[index];
}
int partition(vector<int>& nums,int start,int end){
int index = start - ;
for(int i = start;i < end;i++){
if(nums[i] < nums[end]){
index++;
if(i != index)
swap(nums[i],nums[index]);
}
}
index++;
swap(nums[end],nums[index]);
return index;
}
};
295. Find Median from Data Stream
使用两个堆进行存储，一个是大根堆，即存储所有较小的数；一个是小根堆，即存储所有较大的数。使用priority_queue来代表大小根堆。
class MedianFinder {
public:
/** initialize your data structure here. */
MedianFinder() {
}
void addNum(int num) {
if(p.size() == || p.top() > num)
p.push(num);
else
q.push(num);
if(p.size() > q.size() + ){
int tmp = p.top();
p.pop();
q.push(tmp);
}
if(q.size() > p.size()){
int tmp = q.top();
q.pop();
p.push(tmp);
}
}
double findMedian() {
return p.size() > q.size() ? p.top() * 1.0 : (p.top() + q.top())/2.0;
}
priority_queue<int,vector<int>,less<int>> p;
priority_queue<int,vector<int>,greater<int>> q;
};