面试题库 › 算法 / 大模型 › 求所有子数组中位数之和(偶数长度取靠左中位数)

求所有子数组中位数之和(偶数长度取靠左中位数)

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

哪些公司问过

百度2

常见岗位:AI 应用 / Agent 开发

答案要点

  1. 中位数定义:区间排序后第 ⌈L/2⌉ 个(从 1 计),偶数长度取靠左的那个
  2. 暴力:固定左端点向右扩展,对顶堆维护靠左中位数,O(n² log n)
  3. 阈值转化:≥t 记 +1、<t 记 −1,靠左中位数 ≥t 等价于区间和 >0
  4. 贡献法:答案 = v1·区间总数 + Σ(v_k − v_{k−1})·(中位数 ≥ v_k 的区间数)
  5. 统计和为正的子数组:前缀和离散化后用树状数组计数,O(n log n)

易错点

面试官常见追问

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

相关面试题