同时找数组最大值和最小值的最少比较次数
哪些公司问过
答案要点
- 朴素做法分别求最大最小,共需2n-2次比较
- 成对比较:两元素先互比,大者比max、小者比min,每对3次
- n为奇数共3(n-1)/2次,n为偶数共3n/2-2次,统一为⌈3n/2⌉-2
- ⌈3n/2⌉-2是基于比较模型的下界,可由对手论证证明
- 比朴素法少约25%比较,时间仍为O(n),空间O(1)
易错点
- 奇偶初始化处理错误,n为偶数时漏掉前两个元素的那一次比较
- 以为把两次遍历合成一次循环就能减少比较,实际每个元素仍比较两次
- 把3n/2说成时间复杂度的改进,渐进复杂度仍是O(n)
面试官常见追问
- 用分治法求最大最小值,比较次数是多少?
- 如果要找最大值和次大值,最少比较几次?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 数组和链表的区别与适用场景173 场
- 经典算法题:最长回文子串、无重复最长子串、最大子数组和141 场
- 合并有序数组与合并区间66 场
- 三数之和:排序加双指针50 场
- 字符串相加(大数加法)20 场
- 字符串匹配:KMP 算法18 场
- 字符串反转的实现与注意事项17 场
- 接雨水问题的三种解法14 场
- 螺旋矩阵遍历14 场
- 两数之和的几种解法12 场