桶排序算法实战：牛客4493题最大间隔问题详解
本帖最后由 19339201706 于 2025-7-19 09:52 编辑https://dajuwangluo.cn/zb_users/upload/2025/06/202506231750657446340445.jpg一、问题背景与算法思路本题要求在一个无序数组中找到排序后相邻元素的最大差值。直接排序后遍历的时间复杂度为O(nlogn)，而题目要求O(n)时间复杂度。我们采用桶排序的变种算法，通过巧妙的分桶策略来优化计算。二、完整代码实现（带详细注释）
class MaxDivision { public: int maxGap(vector& nums) { if (nums.size() < 2) return 0; // 边界条件处理
// 找出数组中的最小值和最大值
int min_val = *min_element(nums.begin(), nums.end());
int max_val = *max_element(nums.begin(), nums.end());
// 计算桶的大小和数量（关键步骤）
int bucket_size = max(1, (max_val - min_val) / ((int)nums.size() - 1));
int bucket_num = (max_val - min_val) / bucket_size + 1;
// 初始化桶（存储每个桶的最小值和最大值）
vector<pair<int, int>> buckets(bucket_num, {INT_MAX, INT_MIN});
// 将元素放入桶中
for (int num : nums) {
int idx = (num - min_val) / bucket_size;// 计算桶索引
buckets.first = min(buckets.first, num);
buckets.second = max(buckets.second, num);
}
// 计算最大间隔（关键步骤）
int max_gap = 0;
int prev_max = min_val;// 前一个非空桶的最大值
for (auto& bucket : buckets) {
if (bucket.first == INT_MAX) continue; // 跳过空桶
max_gap = max(max_gap, bucket.first - prev_max);
prev_max = bucket.second;// 更新前一个非空桶的最大值
}
return max_gap;
}
int findMaxDivision(vector<int> A, int n) {
MaxDivision div;
return div.maxGap(A);// 接口适配函数
}
};
三、关键算法要点
[*]分桶策略：根据数组长度动态计算桶的大小和数量
[*]桶内存储：每个桶只记录最小值和最大值
[*]间隔计算：最大间隔一定出现在相邻非空桶之间
[*]边界处理：处理空桶和最小/最大值的情况
四、复杂度分析
[*]时间复杂度：O(n) （3次线性遍历）
[*]空间复杂度：O(n) （桶的存储空间）
五、常见错误提醒
[*]忘记处理数组长度小于2的情况
[*]桶大小计算错误（必须至少为1）
[*]没有正确处理空桶的情况
[*]初始prev_max值设置错误
六、学习价值通过本题可以掌握：
[*]桶排序的变种应用
[*]线性时间复杂度的排序相关问题解法
[*]分桶策略的设计思路
[*]极值问题的优化处理方法
来源：大矩学习资料
页:
[1]