桶排序！！

算法描述

给定一个整数数组 nums 和一个整数 k ，请返回其中出现频率前 k 高的元素。可以按 任意顺序 返回答案。

bucketSort函数

这个函数将输入数组根据元素出现的频率进行排序，并将结果存入桶（bucket）中。

bucketSort完整代码

void bucketSort(ArrayType& items, vector<vector<BucketType>>& bucket)
{unordered_map<BucketType, int> hash;int n = items.size();for (auto& x : items)hash[x]++;                                             // 1for (int i = 0; i <= n; i++)bucket.push_back({});                                  // 2for (auto it = hash.begin(); it != hash.end(); it++)bucket[it->second].push_back(it->first);               // 3for (int i = 0; i <= n; i++)sort(bucket[i].begin(), bucket[i].end());              // 4
}

1. 计数：遍历items数组，将每个元素及其出现次数存入hash哈希表中。
2. 初始化桶：创建一个大小为n+1的桶数组bucket。每个桶是一个vector，起始为空。
3. 分配元素到桶：根据哈希表中的频率，将元素放入对应频率的桶中。例如，出现频率为3的元素会被放入bucket[3]中。
4. 桶内排序：对每个桶内部的元素进行排序。

topKFrequent函数

这个函数调用 bucketSort 对输入数组进行预处理，然后从桶中提取出出现频率最高的 k 个元素。

topKFrequent完整代码

vector<int> topKFrequent(vector<int>& nums, int k)
{vector<vector<BucketType>> bucket;vector<int> res;                                          // 1bucketSort(nums, bucket);                                 // 2for (int i = bucket.size() - 1; i >= 0; i--)              // 3.1{for (int j = bucket[i].size() - 1; j >= 0; j--)       // 3.2{res.push_back(bucket[i][j]);                      // 3.3if (--k == 0)return res;}}return res;
}

1. 初始化：定义一个二维向量bucket来存桶，一个向量res来存储结果。
2. 调用bucketSort：对nums数组进行桶排序，将结果存储在bucket中。
3. 收集结果：
   • 从后向前遍历桶数组（从高频率向低频率）。
   • 从每个桶内部的末尾向前遍历元素（因为桶内部已经排好序）
   • 将元素加入结果res中，直到收集到k个元素。

完整代码

#include <iostream>
#include <map>
#define BucketType int
#define ArrayType vector<int>
using namespace std;void bucketSort(ArrayType& items, vector<vector<BucketType>>& bucket)
{unordered_map<BucketType, int> hash;int n = items.size();//将每个元素放入哈希表进行计数for (auto& x : items)hash[x]++;//初始化桶，起初都为空for (int i = 0; i <= n; i++)bucket.push_back({});//把元素塞入对应的桶for (auto it = hash.begin(); it != hash.end(); it++)bucket[it->second].push_back(it->first);//桶内排序for (int i = 0; i <= n; i++)sort(bucket[i].begin(), bucket[i].end());
}
vector<int> topKFrequent(vector<int>& nums, int k)
{vector<vector<BucketType>> bucket;vector<int> res;bucketSort(nums, bucket);for (int i = bucket.size() - 1; i >= 0; i--){for (int j = bucket[i].size() - 1; j >= 0; j--){res.push_back(bucket[i][j]);if (--k == 0)return res;}}return res;
}
int main()
{vector<int> nums = {1, 1, 1, 2, 2, 3};int k = 2;vector<int> result = topKFrequent(nums, k);for (int num : result){cout << num << " ";}cout << endl;return 0;
}