排序后相邻元素的最大差值(桶排序)
哪些公司问过
答案要点
- 朴素做法:排序后遍历相邻元素,O(n log n)
- 最大间距至少为 (max−min)/(n−1),据此确定桶宽
- 每个桶只维护最小值和最大值
- 答案只可能出现在相邻非空桶之间:后桶最小值减前桶最大值
- 整体时间、空间 O(n),需处理元素少于 2 个和全相等的情况
易错点
- 桶宽计算为 0 导致除零
- 遍历时没有跳过空桶
- 忘记处理数组长度小于 2 的情况
面试官常见追问
- 为什么桶内差值不可能是答案?
- 还有其他线性做法吗?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 常见排序算法的对比129 场
- 排序算法的稳定性58 场
- 归并排序的实现与特点24 场
- 堆排序的实现21 场
- 外排序:10 亿个整数如何排序14 场
- C++ std::sort 的内部实现7 场
- 手写实现一种数组排序算法7 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场