目录
215.数组中的第k个最大元素
347.前k个高频元素
451.根据字符出现频率排序
75.颜色分类
思路：我们可以采用快速排序的分割函数来解决此问题，我们知道，一趟快速排序之后，数组会以某一个值为分割点，使数组的前半部分都小于这个数，后半部分都大于这个数。因此我们可以在每趟的快速排序中，将这个数的最终位置进行返回、判断，来求得在排序之后基准值在第k处的数字即可。
代码实现：
class Solution { public: int findKthLargest(vector<int>& nums, int k) { if(nums.empty()||k<0||k>nums.size()) return - 1; k = nums.size()-k; int index = 0; int start = 0; int end = nums.size()-1; while(1) { index = quick(nums,start,end); if(index==k) break; else if(index<k) start = index +1; else end = index -1; } return nums[index]; } //快排分割函数 int quick(vector<int>&nums,int i,int j) { int start = i; int end = j; int temp = nums[start]; while(start<end) { while(nums[end]>temp&&start<end) { --end; } if(start<end) { nums[start]=nums[end]; ++start; } while(nums[start]<temp&&start<end) { ++start; } if(start<end) { nums[end]=nums[start]; --end; } } nums[start] = temp; return start; } };思路：这个问题和topK问题一样，我们可以先用map表等相关容器对每个数字出现的次数进行统计，然后巧妙的构造一个容量为K的小根堆来求出前k个出现次数最多的元素。
代码实现：
class Solution { public: template<typename T> class Greater { public: bool operator()(T a,T b) { return a.second>b.second; } }; vector<int> topKFrequent(vector<int>& nums, int k) { //统计频率 map<int,int> m; for(auto e: nums) { auto it = m.find(e); if(it==m.end()) { m.insert(make_pair(e,0)); } else { it->second++; } } using type = pair<int,int>; //构建小根堆 priority_queue<type,vector<type>,Greater<type>> que; auto it = m.begin(); while(k&&it!=m.end()) { que.push(*it); ++it; --k; } while(it!=m.end()) { if(it->second >que.top().second) { que.pop(); que.push(*it); } ++it; } vector<int> v; while(!que.empty()) { v.push_back(que.top().first); que.pop(); } return v; } };思路：对于此问题，我们可以先统计每个字符出现的次数，然后按照次数进行排序，最后输出即可。这里巧妙的使用了函数对象来作为排序中的比较方式，当然也可以用lambda表达式来替代。
代码实现：
class Solution { public: template<typename T> class Greater { public: bool operator()(T &a,T& b) { return a.num>b.num; } }; struct Node { Node(char c,int n = 0) { ch = c; num = n; } char ch; int num; }; string frequencySort(string s) { map<char,int> m; //统计次数 for(auto e: s) { auto it = m.find(e); if(it==m.end()) m.insert(make_pair(e,1)); else it->second++; } vector<Node> v; for(auto e:m) { v.push_back(Node(e.first,e.second)); } sort(v.begin(),v.end(),Greater<Node>()); string res; for(auto e:v) { for(int n = 0;n<e.num;++n) res += e.ch; } return res; } };思路：这个问题其实也就使一个排序的问题，就是将0,1,2按照顺序排好，由于只有三个数字，因此我们可以投机取巧，在O(n)的时间复杂度内完成排序算法。具体见代码。
代码实现：
class Solution { public: void sortColors(vector<int>& nums) { int zero = -1,one = 0,two = nums.size(); while(one<two) { if(nums[one] ==0) { swap(nums,++zero,one++); } else if(nums[one]==2) { swap(nums,one,--two); } else { ++one; } } } void swap(vector<int>&nums,int i,int j) { int temp = nums[i]; nums[i]= nums[j]; nums[j] = temp; } };
