面试题库 › 算法 / 大模型 › 同时找数组最大值和最小值的最少比较次数

同时找数组最大值和最小值的最少比较次数

难度 ★★☆在 1 场真实面经中被问到 方向:算法 / 大模型考点:数组与字符串

哪些公司问过

快手1

常见岗位:C++ 后端

答案要点

  1. 朴素做法分别求最大最小,共需2n-2次比较
  2. 成对比较:两元素先互比,大者比max、小者比min,每对3次
  3. n为奇数共3(n-1)/2次,n为偶数共3n/2-2次,统一为⌈3n/2⌉-2
  4. ⌈3n/2⌉-2是基于比较模型的下界,可由对手论证证明
  5. 比朴素法少约25%比较,时间仍为O(n),空间O(1)

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题