题目描述
思路解析动画文字版
记牢两步:先数出每个值的个数,再一轮一轮把还有剩的值各取一个建成一行。下面每一帧都在套这两步。
阶段一 · 准备计数：右边这张是计数表,现在还空着。下面从左到右扫一遍 nums,看到一个数,就把它在表里的个数加 1。这一遍扫完,就知道每个值到底出现了几次。
计数 · 第 0 个是 1：扫到 nums[0] = 1,把 1 的计数加 1,现在计数[1] = 1。计数表记的就是每个值在 nums 里出现了几次。
计数 · 第 1 个是 3：扫到 nums[1] = 3,把 3 的计数加 1,现在计数[3] = 1。计数表记的就是每个值在 nums 里出现了几次。
计数 · 第 2 个是 4：扫到 nums[2] = 4,把 4 的计数加 1,现在计数[4] = 1。计数表记的就是每个值在 nums 里出现了几次。
计数 · 第 3 个是 1：扫到 nums[3] = 1,把 1 的计数加 1,现在计数[1] = 2。计数表记的就是每个值在 nums 里出现了几次。
计数 · 第 4 个是 2：扫到 nums[4] = 2,把 2 的计数加 1,现在计数[2] = 1。计数表记的就是每个值在 nums 里出现了几次。
计数 · 第 5 个是 3：扫到 nums[5] = 3,把 3 的计数加 1,现在计数[3] = 2。计数表记的就是每个值在 nums 里出现了几次。
计数 · 第 6 个是 1：扫到 nums[6] = 1,把 1 的计数加 1,现在计数[1] = 3。计数表记的就是每个值在 nums 里出现了几次。
阶段一完成 · 计数表建好：7 个数全数完了。看这张表:1 出现 3 次最多,2 和 4 各 1 次,3 出现 2 次。出现最多的值 1 有 3 个,这 3 个 1 必须落在 3 个不同的行里,所以最终答案铁定是 3 行。接下来一轮一轮把行建出来。
第 1 轮 · 开新的一行：开始建第 1 行。看计数表,现在还有剩余的值是 1、2、3、4 这 4 个。这一轮的任务,就是把它们每个各取一个,凑成第 1 行,取一个就把对应计数减 1。
第 1 轮 · 取值 1：从计数表取一个 1 放进第 1 行,计数[1] 还剩 2 个,留给后面的轮次。这一行目前是 [1]。
第 1 轮 · 取值 2：从计数表取一个 2 放进第 1 行,计数[2] 减到 0,2 用光了,就从表里划掉,以后的轮次不会再碰它。这一行目前是 [1,2]。
第 1 轮 · 取值 3：从计数表取一个 3 放进第 1 行,计数[3] 还剩 1 个,留给后面的轮次。这一行目前是 [1,2,3]。
第 1 轮 · 取值 4：从计数表取一个 4 放进第 1 行,计数[4] 减到 0,4 用光了,就从表里划掉,以后的轮次不会再碰它。这一行目前是 [1,2,3,4]。
第 1 轮完成 · 第 1 行 = [1,2,3,4]：第 1 行凑齐了,是 [1,2,3,4],里面的数互不相同,合规。计数表里还剩 3 个数没安置,继续开下一轮。
第 2 轮 · 开新的一行：开始建第 2 行。看计数表,现在还有剩余的值是 1、3 这 2 个。这一轮的任务,就是把它们每个各取一个,凑成第 2 行,取一个就把对应计数减 1。
第 2 轮 · 取值 1：从计数表取一个 1 放进第 2 行,计数[1] 还剩 1 个,留给后面的轮次。这一行目前是 [1]。
第 2 轮 · 取值 3：从计数表取一个 3 放进第 2 行,计数[3] 减到 0,3 用光了,就从表里划掉,以后的轮次不会再碰它。这一行目前是 [1,3]。
第 2 轮完成 · 第 2 行 = [1,3]：第 2 行凑齐了,是 [1,3],里面的数互不相同,合规。计数表里还剩 1 个数没安置,继续开下一轮。
第 3 轮 · 开新的一行：开始建第 3 行。看计数表,现在还有剩余的值是 1 这 1 个。这一轮的任务,就是把它们每个各取一个,凑成第 3 行,取一个就把对应计数减 1。
第 3 轮 · 取值 1：从计数表取一个 1 放进第 3 行,计数[1] 减到 0,1 用光了,就从表里划掉,以后的轮次不会再碰它。这一行目前是 [1]。
第 3 轮完成 · 第 3 行 = [1]：第 3 行凑齐了,是 [1]。这一取,计数表全部清空,再没有剩下的数,循环到此结束。
回放 · 答案 3 行：三轮走完,计数表空了。第一行 [1,2,3,4] 把当时四个不同的值各取一个;第二行 [1,3] 取走剩下的 1 和 3;第三行 [1] 收掉最后一个 1。三个 1 恰好分在三行,和一开始说的最少 3 行对上了。
边界想清:单元素一行、全不同一行、同值出现 k 次就得 k 行每行一个。
面试重点:计数加逐轮各取一个、行数等于最大出现次数是最优、注意归零删键与遍历时别边删边遍历。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *from string import *from operator import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def findMatrix(self, nums: List[int]) -> List[List[int]]: cnt = Counter(nums) ans = [] while cnt: row = [] for x in sorted(list(cnt)): row.append(x) cnt[x] -= 1 if cnt[x] == 0: del cnt[x] ans.append(row) return ans复杂度
- 时间：O(n log m)，n 是 nums 的长度,m 是不同数字的个数。第一遍计数是 O(n)。建行阶段每取一个数就让某个计数减 1,取值操作总量是 n;但这里用 sorted / map / TreeMap 这类有序容器,每次操作带一个 log m 的开销,所以整体是 O(n log m)。m 最多和 n 一样大,最坏就退化成 O(n log n)
- 空间：O(n)，计数表最多存 m 个不同的键,不超过 n,是 O(n)。答案二维数组正好装下全部 n 个元素,也是 O(n)。若不把返回值算进额外空间,则额外空间就是那张计数表的 O(n)
易错点
面试追问把动画讲成自己的话
追问这题的核心思路一句话怎么说?
追问为什么这样得到的行数是最少的?
追问实现上有什么要小心的细节?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
缺失的第一个正数
LeetCode 41 · 困难 · 沿着 数组套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题