最大间距问题与桶排序优化
哪些公司问过
答案要点
- 鸽巢原理:n 个数放入 n+1 个等宽桶,必有空桶
- 桶内差值小于桶宽,跨空桶差值不小于桶宽,最大间距只在相邻非空桶之间
- 每个桶只记录 min 和 max,无需桶内排序
- 遍历非空桶,用当前桶 min 减前一非空桶 max 更新答案,时间 O(n)、空间 O(n)
- 边界:元素少于 2 个、全部相等、最大值桶号越界、浮点精度
易错点
- 直接排序再扫描,复杂度 O(n log n),不满足要求
- 在桶内做排序,增加不必要的开销
- max 等于 min 时除以零,或者最大值桶号越界
面试官常见追问
- 如果是整数数组,还有别的线性做法吗?
- 桶的数量能用 n−1 吗?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 常见排序算法的对比129 场
- 排序算法的稳定性58 场
- 归并排序的实现与特点24 场
- 堆排序的实现21 场
- 外排序:10 亿个整数如何排序14 场
- C++ std::sort 的内部实现7 场
- 手写实现一种数组排序算法7 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场