当前位置: 首页> 文旅> 酒店 > 桶排序!!

桶排序!!

时间:2025/7/11 19:25:32来源:https://blog.csdn.net/lils_0222/article/details/139705526 浏览次数:0次

桶排序

  • 算法描述
    • 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]++;                                             // 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;
}
关键字:桶排序!!

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: