Medium

题目描述

给你一个整数数组 nums。你需要从 nums 创建一个 2D 数组，满足以下条件：

  • 2D 数组应该只包含数组 nums 中的元素。
  • 2D 数组每一行包含 不同 的整数。
  • 2D 数组的行数应该是 最小 的。

返回结果数组。如果存在多个答案，返回其中 任意一个 。

注意，2D 数组的每一行上可以含有不同数量的元素。

示例 1：

输入：nums = [1,3,4,1,2,3,1]
输出：[[1,3,4,2],[1,3],[1]]
解释：我们可以创建包含以下几行的 2D 数组：
- 1,3,4,2
- 1,3
- 1
nums 中的所有元素都有用到，2D 数组的每一行都由不同的整数组成，所以这是一个符合题目要求的答案。
可以证明无法设计出只有 2 行或更少行数且符合要求的答案。

示例 2：

输入：nums = [1,2,3,4]
输出：[[4,3,2,1]]
解释：数组中所有元素都不相同，所以我们可以把所有元素都放在 2D 数组的第一行中。

提示：

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= nums.length

解题思路

这道题的核心是理解"行数最小"的含义：每个元素在每行中最多只能出现一次，所以某个数字出现的次数决定了需要的行数。

有两种主要的解题思路：

方法一：频率统计法

  • 统计每个数字的出现次数
  • 最大频次就是所需的行数
  • 按频次分配，第i次出现的数字放在第(i-1)行

方法二：贪心放置法

  • 遍历数组中的每个元素
  • 对于每个元素，尝试将其放入现有的行中（该行还没有这个元素）
  • 如果所有现有行都包含该元素，则创建新行

方法一的思路更直观，代码也更简洁，是推荐解法。方法二虽然更符合直觉的"逐个放置"思路，但实现稍复杂。

两种方法的时间复杂度都是O(n)，但方法一的常数因子更小，且代码更易理解。

代码实现

class Solution {
public:
    vector<vector<int>> findMatrix(vector<int>& nums) {
        unordered_map<int, int> count;
        int maxFreq = 0;
        
        // 统计每个数字的频次
        for (int num : nums) {
            count[num]++;
            maxFreq = max(maxFreq, count[num]);
        }
        
        // 创建结果数组
        vector<vector<int>> result(maxFreq);
        
        // 按频次分配到不同行
        for (auto& [num, freq] : count) {
            for (int i = 0; i < freq; i++) {
                result[i].push_back(num);
            }
        }
        
        return result;
    }
};

class Solution:
    def findMatrix(self, nums: List[int]) -> List[List[int]]:
        from collections import Counter
        
        count = Counter(nums)
        max_freq = max(count.values())
        
        result = [[] for _ in range(max_freq)]
        
        for num, freq in count.items():
            for i in range(freq):
                result[i].append(num)
        
        return result

public class Solution {
    public IList<IList<int>> FindMatrix(int[] nums) {
        var count = new Dictionary<int, int>();
        int maxFreq = 0;
        
        // 统计频次
        foreach (int num in nums) {
            count[num] = count.GetValueOrDefault(num, 0) + 1;
            maxFreq = Math.Max(maxFreq, count[num]);
        }
        
        // 创建结果数组
        var result = new List<IList<int>>();
        for (int i = 0; i < maxFreq; i++) {
            result.Add(new List<int>());
        }
        
        // 分配到不同行
        foreach (var kvp in count) {
            int num = kvp.Key;
            int freq = kvp.Value;
            for (int i = 0; i < freq; i++) {
                result[i].Add(num);
            }
        }
        
        return result;
    }
}

var findMatrix = function(nums) {
    const count = new Map();
    let maxFreq = 0;
    
    // 统计频次
    for (const num of nums) {
        count.set(num, (count.get(num) || 0) + 1);
        maxFreq = Math.max(maxFreq, count.get(num));
    }
    
    // 创建结果数组
    const result = Array.from({length: maxFreq}, () => []);
    
    // 分配到不同行
    for (const [num, freq] of count) {
        for (let i = 0; i < freq; i++) {
            result[i].push(num);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型频率统计法
时间复杂度O(n)
空间复杂度O(n)

其中 n 是数组长度。时间复杂度主要来自遍历数组统计频次和构建结果数组，空间复杂度主要来自哈希表存储频次和结果数组。