面试题库 › C++ / 后端 › 两个有序数组的中位数

两个有序数组的中位数

难度 ★★★在 11 场真实面经中被问到 方向:C++ / 后端考点:查找算法

哪些公司问过

腾讯2字节跳动1快手1华为1拼多多1微软1小红书1深信服1网易互娱1

常见岗位:C/C++ 软件开发、NLP / 语音、后端开发、C++ 后端、Java 后端

答案要点

  1. 暴力:归并后取中位数,O(m+n);要求 O(log(m+n)) 必须用二分
  2. 转化为求两个有序数组合并后的第 k 小元素,k 为中间位置
  3. 划分法:对较短数组二分,使左半元素个数为 (m+n+1)/2,且左半最大值不大于右半最小值
  4. 奇数取左半最大值,偶数取左半最大值与右半最小值的平均
  5. 边界:某数组为空、划分点在端点,用正负无穷哨兵;复杂度 O(log(min(m,n)))

易错点

面试官常见追问

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

相关面试题