SWE · Coding

相同数字分组且组大小不同:频次去重判定

每个值恰一个组,不同值的出现次数不能重复。

题目重点:每个值恰一个组,不同值的出现次数不能重复。

题意与假设

这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。

  • 训练合同同值全部且仅放同一组,不同值不能混组;必须使用所有元素。
  • 空输入按空分组可行。连续顺子follow-up的最小长度未给,不用默认单元素组猜答案。

解题路线

  1. Counter统计各值count,形成频次数组。若频次set大小等于不同值数,则所有组大小互异,True。
  2. 任何重复次数对应两组必相同大小,没有调整余地,因为不允许拆同值或混不同值。没有重复频次则按值分组直接构造可行方案。
  3. 顺子条件改变了分组性质,需要明确每组长度、能否复用值/不同长度/全部元素;例子暗示非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贪心及证明?
✓已复制微信号!