215. 数组中的第K个最大元素（快排+二分）

使用的快速排序加二分
这里出现了很多错误，建议还是使用快排的标准模式。
注意使用数组随机化，防止最坏情况的出现，时间代价的期望是O(n)

快排写法

  1. class Solution {
  2. public:
  3.     void randomsort(vector<int>& nums){//数组随机化
  4.         for(int i = 0; i < nums.size(); i++){
  5.             int j = rand()%nums.size();
  6.             swap(nums[i], nums[j]);
  7.         }
  8.     } 
  9.     int findKthLargest(vector<int>& nums, int k) {
  10.         srand(time(0));
  11.         randomsort(nums);
  12.         int l = 0, n = nums.size(), r = nums.size();
  13.         while(l < r){
  14.             int mid = quick_sort(nums, l , r);
  15.             if(mid == n - k){
  16.                 return nums[mid];
  17.             } else if(mid > n-k){
  18.                 r = mid;
  19.             } else {
  20.                 l = mid + 1;
  21.             }
  22.         }
  23.         return nums[l];
  24.     }
  25.     int quick_sort(vector<int>& nums, int l, int r){
  26.          if(l+1 >= r){
  27.              return l;
  28.         }
  29.         int p = l, q = r - 1, key = nums[l];
  30.         while(p < q){
  31.             while(p < q&&nums[q] >= key){
  32.                 q--;
  33.             }
  34.             nums[p] = nums[q];
  35.             while(p < q&&nums[p] <= key){
  36.                 p++;
  37.             }
  38.             nums[q] = nums[p];
  39.         }
  40.         nums[p] = key;
  41.         return p;
  42.     }
  43. };

堆排写法

堆排写法效率高一点。

  1. class Solution {
  2. public:
  3.     void maxHeapify(vector<int>& a, int i, int heapSize) {
  4.         int l = i * 2 + 1, r = i * 2 + 2, largest = i;
  5.         if (l < heapSize && a[l] > a[largest]) {
  6.             largest = l;
  7.         } 
  8.         if (r < heapSize && a[r] > a[largest]) {
  9.             largest = r;
  10.         }
  11.         if (largest != i) {
  12.             swap(a[i], a[largest]);
  13.             maxHeapify(a, largest, heapSize);
  14.         }
  15.     }
  17.     void buildMaxHeap(vector<int>& a, int heapSize) {
  18.         for (int i = heapSize / 2; i >= 0; --i) {
  19.             maxHeapify(a, i, heapSize);
  20.         } 
  21.     }
  23.     int findKthLargest(vector<int>& nums, int k) {
  24.         int heapSize = nums.size();
  25.         buildMaxHeap(nums, heapSize);
  26.         for (int i = nums.size() - 1; i >= nums.size() - k + 1; --i) {
  27.             swap(nums[0], nums[i]);
  28.             --heapSize;
  29.             maxHeapify(nums, 0, heapSize);//这里每次将堆顶值与最小值进行调换，但是只调整堆顶值，来模拟删除的效果。
  30.         }
  31.         return nums[0];
  32.     }
  33. };

347. 前 K 个高频元素（堆排，桶排）

堆排

使用优先队列实现堆排。
时间复杂度：O（klogn）

  1. class Solution {
  2. public:
  3.     static bool cmp(pair<int, int>& m, pair<int, int>& n) {
  4.         return m.second < n.second;
  5.     }
  7.     vector<int> topKFrequent(vector<int>& nums, int k) {
  8.         unordered_map<int, int> occurrences;
  9.         for (auto& v : nums) {
  10.             occurrences[v]++;
  11.         }
  13.         // pair 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
  14.         priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(&cmp)> q(cmp);
  15.         for (auto& [num, count] : occurrences) {
  16.             q.emplace(num, count);
  17.         }
  18.         vector<int> ret;
  19.         while (!q.empty()) {
  20.             if(ret.size() == k){
  21.                 break;
  22.             }
  23.             ret.emplace_back(q.top().first);
  24.             q.pop();
  25.         }
  26.         return ret;
  27.     }
  28. };

桶排

用桶装相同的数，频次越大桶越大。维护一个max_count是桶的最大值，维护一个buckets，第一维桶的大小，第二维是有这个频次的元素。max_count慢慢往下减直到获得k个元素，满足条件。
时间复杂度：O(N)

  1. class Solution {
  2. public:
  3.     vector<int> topKFrequent(vector<int>& nums, int k) {
  4.         unordered_map<int, int> counts;
  5.         int max_count = 0;
  6.         for(const int & num : nums){
  7.             max_count = max(max_count, ++counts[num]);
  8.         }
  9.         vector<vector<int>> buckets(max_count+1);
  10.         for(const auto &p : counts){
  11.             buckets[p.second].push_back(p.first);
  12.         }
  13.         vector<int> ans;
  14.         for(int i = max_count; i >= 0&&ans.size() < k; --i){
  15.             for(const int &num : buckets[i]){
  16.                 ans.push_back(num);
  17.                 if(ans.size() == k) {
  18.                     break;
  19.                 }
  20.             }
  21.         }
  22.         return ans;
  23.     }
  24. };

451. 根据字符出现频率排序（hash）

哈希sort

缺点：花费时间较多，因为哈希表的取数据虽然时间复杂度为O（1），但是嵌入sort函数中作为cmp函数的条件的话会被调用nlogn次，花费很多时间。
优点：代码简洁

  1. class Solution {
  2. public:
  3.     string frequencySort(string s) {
  4.         unordered_map<char, int> mp;
  5.         for(auto ch:s) mp[ch]++;
  6.         sort(s.begin(),s.end(),[&](const char &a, const char &b){
  7.             return mp[a]==mp[b] ? a>b:mp[a] > mp[b];
  8.         });
  9.         return s;
  10.     }
  11. };
  12. //此处耗时久的原因是因为，hash表的查询也需要时间。

使用迭代器

  1. class Solution {
  2. public:
  3.     string frequencySort(string s) {
  4.         string ans;
  5.         unordered_map<char, int> hash;
  6.         for(auto c : s){
  7.             hash[c]++;
  8.         }
  9.         vector<pair<char, int>> vec;
  10.         for(auto it = hash.begin(); it != hash.end(); it++){
  11.             vec.push_back(*it);
  12.         }
  13.         sort(vec.begin(), vec.end(),cmp);
  14.         for(auto i = vec.begin(); i != vec.end(); i++){
  15.             for(int j = 0; j < i->second; j++){
  16.                 ans+=i->first;
  17.             }
  18.         }
  19.         return ans;
  20.     }
  21.     static bool cmp(pair<char, int> & a, pair<char, int> &b){
  22.         return a.second > b.second;
  23.     } 
  24. };