桶排序！！

桶排序

• 算法描述
• • bucketSort函数
  • bucketSort完整代码
  • topKFrequent函数
  • topKFrequent完整代码
• 完整代码

算法描述

给定一个整数数组 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]++;                                             // 1
    for (int i = 0; i <= n; i++)
        bucket.push_back({});                                  // 2
    for (auto it = hash.begin(); it != hash.end(); it++)
        bucket[it->second].push_back(it->first);               // 3
    for (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;                                          // 1
    bucketSort(nums, bucket);                                 // 2
    for (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.3
            if (--k == 0)
                return res;
        }
    }
    return res;
}

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

完整代码

#include 
#include 
#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;
}