LeetCode 2610中等数组 · 哈希
转换二维数组 图解题解
这道题到底在问什么
给定整数数组 nums。请构造一个二维数组,满足:只包含 nums 中的元素;每一行内的整数互不相同;行数尽可能少。每一行的元素个数可以不同。返回任意一种合法结果。
- 输入
- nums=[1,3,4,1,2,3,1]
- 输出
- [[1,2,3,4],[1,3],[1]]
- 输入
- nums=[1,2,3,4]
- 输出
- [[1,2,3,4]]
最优解：一步一步想明白
- 3记牢两步:先数出每个值的个数,再一轮一轮把还有剩的值各取一个建成一行。下面每一帧都在套这两步。
- 4右边这张是计数表,现在还空着。下面从左到右扫一遍 nums,看到一个数,就把它在表里的个数加 1。这一遍扫完,就知道每个值到底出现了几次。
- 5扫到 nums[0] = 1,把 1 的计数加 1,现在计数[1] = 1。计数表记的就是每个值在 nums 里出现了几次。
- 6扫到 nums[1] = 3,把 3 的计数加 1,现在计数[3] = 1。计数表记的就是每个值在 nums 里出现了几次。
- 7扫到 nums[2] = 4,把 4 的计数加 1,现在计数[4] = 1。计数表记的就是每个值在 nums 里出现了几次。
- 8扫到 nums[3] = 1,把 1 的计数加 1,现在计数[1] = 2。计数表记的就是每个值在 nums 里出现了几次。
- 9扫到 nums[4] = 2,把 2 的计数加 1,现在计数[2] = 1。计数表记的就是每个值在 nums 里出现了几次。
- 10扫到 nums[5] = 3,把 3 的计数加 1,现在计数[3] = 2。计数表记的就是每个值在 nums 里出现了几次。
- 11扫到 nums[6] = 1,把 1 的计数加 1,现在计数[1] = 3。计数表记的就是每个值在 nums 里出现了几次。
- 127 个数全数完了。看这张表:1 出现 3 次最多,2 和 4 各 1 次,3 出现 2 次。出现最多的值 1 有 3 个,这 3 个 1 必须落在 3 个不同的行里,所以最终答案铁定是 3 行。接下来一轮一轮把行建出来。
- 13开始建第 1 行。看计数表,现在还有剩余的值是 1、2、3、4 这 4 个。这一轮的任务,就是把它们每个各取一个,凑成第 1 行,取一个就把对应计数减 1。
- 14从计数表取一个 1 放进第 1 行,计数[1] 还剩 2 个,留给后面的轮次。这一行目前是 [1]。
- 15从计数表取一个 2 放进第 1 行,计数[2] 减到 0,2 用光了,就从表里划掉,以后的轮次不会再碰它。这一行目前是 [1,2]。
- 16从计数表取一个 3 放进第 1 行,计数[3] 还剩 1 个,留给后面的轮次。这一行目前是 [1,2,3]。
- 17从计数表取一个 4 放进第 1 行,计数[4] 减到 0,4 用光了,就从表里划掉,以后的轮次不会再碰它。这一行目前是 [1,2,3,4]。
- 18第 1 行凑齐了,是 [1,2,3,4],里面的数互不相同,合规。计数表里还剩 3 个数没安置,继续开下一轮。
- 19开始建第 2 行。看计数表,现在还有剩余的值是 1、3 这 2 个。这一轮的任务,就是把它们每个各取一个,凑成第 2 行,取一个就把对应计数减 1。
- 20从计数表取一个 1 放进第 2 行,计数[1] 还剩 1 个,留给后面的轮次。这一行目前是 [1]。
- 21从计数表取一个 3 放进第 2 行,计数[3] 减到 0,3 用光了,就从表里划掉,以后的轮次不会再碰它。这一行目前是 [1,3]。
- 22第 2 行凑齐了,是 [1,3],里面的数互不相同,合规。计数表里还剩 1 个数没安置,继续开下一轮。
- 23开始建第 3 行。看计数表,现在还有剩余的值是 1 这 1 个。这一轮的任务,就是把它们每个各取一个,凑成第 3 行,取一个就把对应计数减 1。
- 24从计数表取一个 1 放进第 3 行,计数[1] 减到 0,1 用光了,就从表里划掉,以后的轮次不会再碰它。这一行目前是 [1]。
- 25第 3 行凑齐了,是 [1]。这一取,计数表全部清空,再没有剩下的数,循环到此结束。
- 26三轮走完,计数表空了。第一行 [1,2,3,4] 把当时四个不同的值各取一个;第二行 [1,3] 取走剩下的 1 和 3;第三行 [1] 收掉最后一个 1。三个 1 恰好分在三行,和一开始说的最少 3 行对上了。
⚠️ 容易写错的地方
✗ 错：为了行数少,把尽量多的数硬塞进第一行
✓ 对：每一轮把还有剩的不同值各取一个
同一行不能有重复值,硬塞会撞重复;逐轮各取一个,行数自然等于最大出现次数,已是理论最少
✗ 错：一轮里给同一个值取了两个
✓ 对：一轮里每个值最多取一个
同一行里出现两个相同的数就违反了每行互不相同的规则,一轮一值是这条规则的直接体现
✗ 错：计数减到 0 后还留在表里继续遍历
✓ 对：减到 0 立刻从计数表删掉
留着 0 会让后面的轮次误以为它还有货,凭空多取或多建空行,必须及时清理
✗ 错：边遍历计数表边删除键
✓ 对：C++/Java 先把要删的键收集起来,遍历完再统一删
在遍历容器的同时改动它的结构会让迭代器失效,引发未定义行为或异常,先收集后删除才安全
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from 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 = right
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class 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 ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
vector<vector<int>> findMatrix(vector<int>& nums) {
map<int, int> cnt;
for (int x : nums) ++cnt[x];
vector<vector<int>> ans;
while (!cnt.empty()) {
vector<int> row;
vector<int> erase;
for (auto& [x, c] : cnt) {
row.push_back(x);
if (--c == 0) erase.push_back(x);
}
for (int x : erase) cnt.erase(x);
ans.push_back(row);
}
return ans;
}
};Java
import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
public List<List<Integer>> findMatrix(int[] nums) {
TreeMap<Integer, Integer> cnt = new TreeMap<>();
for (int x : nums) cnt.put(x, cnt.getOrDefault(x, 0) + 1);
List<List<Integer>> ans = new ArrayList<>();
while (!cnt.isEmpty()) {
ArrayList<Integer> row = new ArrayList<>();
ArrayList<Integer> remove = new ArrayList<>();
for (Map.Entry<Integer, Integer> e : cnt.entrySet()) {
row.add(e.getKey());
int next = e.getValue() - 1;
e.setValue(next);
if (next == 0) remove.add(e.getKey());
}
for (int x : remove) cnt.remove(x);
ans.add(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)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 转换二维数组 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题的核心思路一句话怎么说?+
先用计数表统计每个值出现几次,再一轮一轮建行,每轮把还有剩余的每个不同值各取一个凑成一行、对应计数减 1、减到 0 就删掉,直到计数表为空。行数正好等于出现次数最多的值的次数,这是理论上的最少行数。
为什么这样得到的行数是最少的?+
任何一个出现 k 次的值,这 k 个相同的数因为每行不能重复,必须分到 k 个不同的行,所以行数下界是所有值里的最大出现次数。而逐轮各取一个的贪心,每轮把每个剩余值消化一个,恰好用最大次数那么多轮清空,达到了这个下界,所以是最优。
实现上有什么要小心的细节?+
一是计数减到 0 要及时把键从表里删掉,否则后面轮次会误判它还有货。二是用 C plus plus 的 map 或 Java 的 TreeMap 时,不要边遍历边删键,应该先把要删的键收集到一个列表,遍历完再统一删,避免迭代器失效。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 转换二维数组 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。