2610-转换二维数组

给你一个整数数组 nums 。请你创建一个满足以下条件的二维数组：

• 二维数组应该 只 包含数组 nums 中的元素。
• 二维数组中的每一行都包含 不同 的整数。
• 二维数组的行数应尽可能 少 。

返回结果数组。如果存在多种答案，则返回其中任何一种。

请注意，二维数组的每一行上可以存在不同数量的元素。

示例 1：

**输入：** nums = [1,3,4,1,2,3,1]
**输出：** [[1,3,4,2],[1,3],[1]]
**解释：** 根据题目要求可以创建包含以下几行元素的二维数组：
- 1,3,4,2
- 1,3
- 1
nums 中的所有元素都有用到，并且每一行都由不同的整数组成，所以这是一个符合题目要求的答案。
可以证明无法创建少于三行且符合题目要求的二维数组。

示例 2：

**输入：** nums = [1,2,3,4]
**输出：** [[4,3,2,1]]
**解释：** nums 中的所有元素都不同，所以我们可以将其全部保存在二维数组中的第一行。

提示：

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

本题视频讲解

见【周赛 339】 。

思路

用一个哈希表 cnt 记录每个元素的剩余次数。构造答案时，如果元素 x 的剩余次数为 0，则将 x 从 cnt 中删除。

[sol1-Python3]

class Solution:
    def findMatrix(self, nums: List[int]) -> List[List[int]]:
        ans = []
        cnt = Counter(nums)
        while cnt:
            ans.append(list(cnt))
            for x in ans[-1]:
                cnt[x] -= 1
                if cnt[x] == 0:
                    del cnt[x]
        return ans

[sol1-Java]

class Solution {
    public List<List<Integer>> findMatrix(int[] nums) {
        var cnt = new HashMap<Integer, Integer>();
        for (int x : nums) cnt.merge(x, 1, Integer::sum);
        var ans = new ArrayList<List<Integer>>();
        while (!cnt.isEmpty()) {
            var row = new ArrayList<Integer>();
            for (var it = cnt.entrySet().iterator(); it.hasNext(); ) {
                var e = it.next();
                row.add(e.getKey());
                e.setValue(e.getValue() - 1);
                if (e.getValue() == 0)
                    it.remove();
            }
            ans.add(row);
        }
        return ans;
    }
}

[sol1-C++]

class Solution {
public:
    vector<vector<int>> findMatrix(vector<int> &nums) {
        unordered_map<int, int> cnt;
        for (int x: nums) ++cnt[x];
        vector<vector<int>> ans;
        while (!cnt.empty()) {
            vector<int> row;
            for (auto it = cnt.begin(); it != cnt.end();) {
                row.push_back(it->first);
                if (--it->second == 0) it = cnt.erase(it);
                else ++it;
            }
            ans.push_back(row);
        }
        return ans;
    }
};

[sol1-Go]

func findMatrix(nums []int) (ans [][]int) {
	cnt := map[int]int{}
	for _, x := range nums {
		cnt[x]++
	}
	for len(cnt) > 0 {
		row := []int{}
		for x := range cnt {
			row = append(row, x)
			if cnt[x]--; cnt[x] == 0 {
				delete(cnt, x)
			}
		}
		ans = append(ans, row)
	}
	return
}

复杂度分析

• 时间复杂度：O(n)，其中 n 为 nums 的长度。
• 空间复杂度：O(n)。