题目重点：选一组不同值并删去它们的所有出现，使删掉元素数至少一半；按频次降序贪心并证明最优。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 同一数值一旦被选，它在数组里的所有出现都删除；成本是选出的不同值数量。
- 删除数量至少 n/2，所以整数阈值为 ceil(n/2)；空数组训练版返回 0。
- 数组元素可正可负，只按值相等计频次。
解题路线
- 先统计每个不同值的出现频次。
- 将频次从大到小排序，依序加入删除集合直到累计移除数达到 ceil(n/2)。
- 交换论证：任何使用 r 种值的方案最多能删掉频次前 r 大的总和，因此若前 r−1 大还不足阈值，不可能有更少种值的解。
- 若值域/频次范围特殊，可用计数桶替代比较排序；通常 distinct 数 d≤n，排序已经足够。
手动走一遍
[1,1,1,2,2,3] 长 6，阈值 3。选择值 1 一种就删 3 个，返回 1；若先选 2 和 3 虽也删 3 个，却用了两种，不最优。奇数长度 5 时至少删 3 个。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections import Counter
from collections.abc import Sequence
def minimum_distinct_values_to_remove_half(values: Sequence[int]) -> int:
"""Remove all copies of selected values until >= half of items are gone."""
target = (len(values) + 1) // 2
if target == 0:
return 0
removed = 0
for selected, count in enumerate(sorted(Counter(values).values(), reverse=True), 1):
removed += count
if removed >= target:
return selected
raise AssertionError('unreachable')
if __name__ == '__main__':
assert minimum_distinct_values_to_remove_half([1, 1, 1, 2, 2, 3]) == 1
复杂度
n 个元素、d 个不同值：计数 O(n) 预期，排序 O(d log d)，空间 O(d)。如用频次桶可在 O(n) 时间/空间内处理。
易错点与追问
容易失分的边界
- 按元素逐个删除计成本，而题目成本是不同值数量。
- 奇数 n 用 floor(n/2) 导致删不到一半。
- 频次从小到大选，结果不最优。
- 把题目误解为‘删掉一半不同整数种类’。
继续深挖
- 若每个值有不同删除成本，频次贪心为何可能失效？
- 若必须恰好删除一半元素但选值会删除所有出现，什么时候无解？
- 在线数据流中频次持续变化，如何维护近似答案？
