在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2 输出: 5 示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4 说明:
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
维持一个包含k个元素的小顶堆，遍历一遍nums,取出堆顶即可。
class Solution { public: int findKthLargest(vector<int>& nums, int k) { priority_queue<int, vector<int>, greater<int>> q; for(auto& x : nums) { q.push(x); if(q.size() > k) q.pop(); } return q.top(); } };利用(从小到大)快排的partition操作把数组两边划分成左边小于等于v, 右边大于等于v。(v为基准值)，位置记为p。 若右边的元素比不少于k个，说明第k大的元素在数组的右边， 否则第k大的元素在数组的左边。 注意： 若右边的元素比少于k个，设右边元素个数为lenR，因为右边边已经有lenR个数比现有的位置大了，所以在在数组左边找 第k - lenR大的数。
该递归函数不消耗空间，因为并不需要保存变量。每次平均把数组砍一半，要不递归左边，或者递归右边。
class Solution { public: int partition(vector<int>& nums, int l, int r) { int x = nums[l+r >> 1]; int i = l - 1, j = r + 1; while(i < j) { do ++i; while(nums[i] < x); do --j; while(nums[j] > x); if(i < j) swap(nums[i], nums[j]); } return j; } int find_num(vector<int>& nums, int l, int r, int k) { if(l >= r) return nums[r]; int p = partition(nums, l, r); return (r - p) >= k ? find_num(nums, p + 1, r, k) : find_num(nums, 0, p, k-(r - p)); } int findKthLargest(vector<int>& nums, int k) { return find_num(nums, 0, nums.size() - 1, k); } };平均 时间：O(n) & 空间：O(1) || 最坏：时间：O(n^2) 空间 O(1)
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2] 示例 2:
输入: nums = [1], k = 1 输出: [1] 说明：
你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
统计nums中每个元素的次数，然后根据次数排序，取出前k个就行了。
class Solution { public: vector<int> topKFrequent(vector<int>& nums, int k) { vector<int> ans; map<int, int> hash; for(auto i : nums) hash[i]++; vector<pair<int, int> > hashv(hash.begin(), hash.end()); sort(hashv.begin(), hashv.end(), [](pair<int, int>& a, pair<int, int>& b) {return a.second > b.second;}); auto h = hashv.begin(); while(k--) { ans.push_back(h->first); h++; } return ans; } };统计nums中每个元素的次数, 然后维护一个包含k个元素的小顶堆, 每次取出堆顶压入栈。
class Solution { public: struct cmp { bool operator()(pair<int, int>& a, pair<int, int>& b) { return a.second > b.second; } }; vector<int> topKFrequent(vector<int>& nums, int k) { vector<int> ans; map<int, int> hash; for(auto i : nums) hash[i]++; priority_queue<pair<int, int>, vector<pair<int, int> >, cmp> pq; for(auto i : hash) { pq.push(i); if(pq.size() > k) pq.pop(); } while(k--) { ans.push_back(pq.top().first); pq.pop(); } return ans; } };给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
示例 1:
输入: “tree”
输出: “eert”
解释: 'e’出现两次，'r’和’t’都只出现一次。 因此’e’必须出现在’r’和’t’之前。此外，"eetr"也是一个有效的答案。 示例 2:
输入: “cccaaa”
输出: “cccaaa”
解释: 'c’和’a’都出现三次。此外，"aaaccc"也是有效的答案。 注意"cacaca"是不正确的，因为相同的字母必须放在一起。 示例 3:
输入: “Aabb”
输出: “bbAa”
解释: 此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。 注意’A’和’a’被认为是两种不同的字符。
记录每个字符出现的次数，然后按次数从大到小排序，最后输出。
class Solution { public: string frequencySort(string s) { map<char, int> h; for(auto c : s) { h[c]++; } vector<pair<char, int> > v(h.begin(), h.end()); sort(v.begin(), v.end(), [](pair<char, int>& a, pair<char, int>& b) {return a.second > b.second;}); string ans = ""; vector<pair<char, int> >::iterator v1 = v.begin(); for(; v1 != v.end(); v1++) { while(v1->second--) ans += v1->first; } return ans; } };记录每个字符出现的次数, 然后维护一个大顶堆，每次取出堆顶出去就好了。
class Solution { public: struct cmp { bool operator()(pair<char, int>& a, pair<char, int>& b) { return a.second < b.second; } }; string frequencySort(string s) { map<char, int> h; for(auto c : s) { h[c]++; } priority_queue<pair<char, int>, vector<pair<char, int> >, cmp> pq; for(auto i : h) pq.push(i); int n = pq.size(); string ans = ""; while(n--) { int j = pq.top().second; while(j--) ans += pq.top().first; pq.pop(); } return ans; } };给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意: 不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2] 进阶：
一个直观的解决方案是使用计数排序的两趟扫描算法。 首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。 你能想出一个仅使用常数空间的一趟扫描算法吗？
