题目重点:每个值恰一个组,不同值的出现次数不能重复。
题意与假设
这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。
- 训练合同同值全部且仅放同一组,不同值不能混组;必须使用所有元素。
- 空输入按空分组可行。连续顺子follow-up的最小长度未给,不用默认单元素组猜答案。
解题路线
- Counter统计各值count,形成频次数组。若频次set大小等于不同值数,则所有组大小互异,True。
- 任何重复次数对应两组必相同大小,没有调整余地,因为不允许拆同值或混不同值。没有重复频次则按值分组直接构造可行方案。
- 顺子条件改变了分组性质,需要明确每组长度、能否复用值/不同长度/全部元素;例子暗示非trivial规则,但不能只凭相似题号认定最少三项。
手动走一遍
[1,2,3,4,2,3,3,4,4,4]频次1/2/3/4,True;[1,2,3]频次皆1,False。[7,7]唯一组大小2,True;[1,1,2,2]两组大小2,False。
Python 参考实现
下面的代码按上文假设实现,适合本地运行并追加自己的测试用例。
代码区可横向滚动;使用键盘时,先聚焦代码区再按方向键查看。
from collections import Counter
def partitionable(a):
counts=list(Counter(a).values())
return len(counts)==len(set(counts))
复杂度
期望O(n)时间、O(d)空间;如果只要是否,可边增频次边维护次数的频数,但最后静态判定最直接。
易错点与追问
容易失分的边界
- 只检查array长度是否不同根本无意义,分组大小来自每值频次。
- 把顺子follow-up当同值分组继续用Counter大小会丢邻接约束。
继续深挖
- 如果允许删最少元素使频次互异,如何贪心分配剩余频次?
- 顺子长度至少3若正式确认,怎样用need/remaining贪心及证明?
