题目描述
给你一个整数数组 nums
。请你创建一个满足以下条件的二维数组:
- 二维数组应该 只 包含数组
nums
中的元素。 - 二维数组中的每一行都包含 不同 的整数。
- 二维数组的行数应尽可能 少。
返回结果数组。如果存在多种答案,则返回其中任何一种。
请注意,二维数组的每一行上可以存在不同数量的元素。
样例
输入:nums = [1,3,4,1,2,3,1]
输出:[[1,3,4,2],[1,3],[1]]
解释:根据题目要求可以创建包含以下几行元素的二维数组:
- 1,3,4,2
- 1,3
- 1
nums 中的所有元素都有用到,并且每一行都由不同的整数组成,所以这是一个符合题目要求的答案。
可以证明无法创建少于三行且符合题目要求的二维数组。
输入:nums = [1,2,3,4]
输出:[[4,3,2,1]]
解释:nums 中的所有元素都不同,所以我们可以将其全部保存在二维数组中的第一行。
限制
1 <= nums.length <= 200
1 <= nums[i] <= nums.length
算法
(哈希表) $O(n)$
- 统计每个数字的出现次数,最终答案的行数就是出现次数最多的数字的出现次数。
- 确定了行数之后,按列填充每个数字。
时间复杂度
- 遍历所有数字存入哈希表一次,再遍历哈希表一次,故总时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储哈希表。
C++ 代码
class Solution {
public:
vector<vector<int>> findMatrix(vector<int>& nums) {
unordered_map<int, int> seen;
for (int x : nums)
++seen[x];
vector<vector<int>> ans;
for (const auto &[k, v] : seen) {
if (ans.size() < v)
ans.resize(v);
for (int i = 0; i < v; i++)
ans[i].push_back(k);
}
return ans;
}
};