题目重点：用配对和斜率两种证明解释中位数最优，处理偶数个点、必须选原点、重复值和 quickselect。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 有 N≥1 个一维实数位置，目标 f(x)=Σ|x-aᵢ|；若必须从已有点中选，仍至少有一个中位位置满足。
- 本题是 L1 距离和，不把平方 L2 或 K 设施选址与之混同。题目未明确坐标范围、是否重复或平局规则。
解题路线
- 先排序 a₁≤…≤aₙ，把最左与最右两点成对。对任意 x，|x-a₁|+|x-aₙ|≥aₙ-a₁，且当 x 在两点之间取等；所有对的交集就是中位区间。奇数时中心点唯一，偶数时 [aₙ/₂,aₙ/₂₊₁] 上每一点同样最优。
- 另一证明看不在样本位置处的斜率：x 左边每点贡献 +1，右边每点贡献 -1；x 从左到右移动，斜率从负变正，零点落在中位区间。
- 只要最优值可用排序 O(N log N) 取中位数；大量值且只求一个中位位置，可用 quickselect 平均 O(N)，最坏 O(N²)，若需保证最坏线性时间要选确定性选择算法。
- 若题目要求最小总距离，取得中位数后再线性求和；累加值可能比单个坐标大，使用宽整数。偶数且只准已有点时两侧中位样本都可。
手动走一遍
点 [1,2,9,10] 的中位区间 [2,9]，x=2 与 x=9 的距离和均为 16；x=5 也为 16，但若只可选已有位置就选 2 或 9。点 [1,2,9] 唯一中位 2，总距离 8。
规模与取舍
排序法 O(N log N) 时间、排序额外空间依实现；quickselect 平均 O(N)、最坏 O(N²)，原地额外空间 O(1) 或递归栈。求距离和另需 O(N)。数学证明本身不依赖坐标是否为整数。
易错点与追问
容易失分的边界
- 说平均值最优，那是平方损失的结论。
- 偶数样本误称唯一中位数。
- 只输出位置却忽略题目若要求总距离。
- 把 K 路由器或 L2 追问套用单点中位数。
- 宣称普通 quickselect 最坏 O(N)。
继续深挖
- 若是二维曼哈顿距离，两个坐标可否分别取中位数？
- 若距离平方和，最优点如何变化？
- 若必须选 K 个房屋位置，如何建模 DP 或聚类？
- 点按权重计入时如何找加权中位数？
