注意multiset的一个bug：

multiset带一个参数的erase函数原型有两种。一是传递一个元素值，如上面例子代码中，这时候删除的是集合中所有值等于输入值的元素，并且返回删除的元素个数；另外一种是传递一个指向某个元素的iterator，这时候删除的就是这个对应的元素，无返回值。

https://www.cnblogs.com/lakeone/p/5600494.html

删除的时候一定不能删除指针，只能删除迭代器

leetcode那个题就是在这个地方出错的：

Input: [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] 20

Output: 3

Expected: 2

如果container.erase(*con)，最后小根堆的大小就只有19个

container.erase(con)才是正确的

 

剑指offer 最小的k个数：

 这是partition版本的

class Solution {public:    vector
     
       GetLeastNumbers_Solution(vector
      
        input, int k) {        vector
       
         result;        int length = input.size();        if(input.empty() || length <= 0 || k <= 0 || length < k)            return result;        int start = 0;        int end = length - 1;        int index = partition(input,start,end);        while(index != k-1){            if(index > k-1){                end = index - 1;                index = partition(input,start,end);            }            else{                start = index + 1;                index = partition(input,start,end);            }        }        for(int i = 0;i < k;i++)            result.push_back(input[i]);        return result;    }    int partition(vector
        
          &input,int start,int end){        int small = start - 1;        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
         
          & input,int a,int b){        int tmp = input[a];        input[a] = input[b];        input[b] = tmp;    }};
         
        
       
      
     

 这是基于大根堆的：

class Solution {public:    vector
     
       GetLeastNumbers_Solution(vector
      
        input, int k) {        vector
       
         output;        int length = input.size();        if(input.empty() || k <= 0 || length < k)            return output;        multiset
        
         
          > numbers;        multiset
          
           
            >::iterator greaternumber; vector
            
             ::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

小根堆

class Solution {public:    int findKthLargest(vector
     
      & nums, int k) {        int length = nums.size();        if(length <= 0 || k <= 0 || length < k)            return -1;        multiset
      
       
        > container;        multiset
        
         
          >::iterator con;        vector
          
           ::iterator it = nums.begin(); for(;it != nums.end();it++){ if(container.size() < k) container.insert(*it); else{ con = container.begin(); if(*con < *it){ container.erase(con); container.insert(*it); } } } int min_num = 0x7FFFFFFF; for(con = container.begin();con != container.end();con++){ if(*con < min_num) min_num = *con; } return min_num; }};