[LeetCode] 每日一题 2610. 转换二维数组 + 集合迭代踩坑

题目链接

https://leetcode.cn/problems/convert-an-array-into-a-2d-array-with-conditions

题目描述

给你一个整数数组 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

解题思路

这道题思路比较直观，就是统计每个元素的出现次数，然后按照出现频率构造二维数组，确保每行元素不重复，同时行数尽可能少

我刚开始写这道题的时候，想的是直接用 HashMap 来存储元素的出现频率，然后用 keySet 遍历去填充二维数组。但在实现过程中，我犯了一个低级错误——在遍历 keySet 的时候，我尝试 remove 掉已经用完的元素，结果直接报错，才意识到迭代集合时不能修改集合。这让我踩了个坑，也顺便加深了对 HashMap 迭代规则的理解

后来我换了一种更直接的思路：用一个数组来存储元素出现的次数，然后按照次数构造二维数组。这样不仅避免了 HashMap 遍历的问题，还提高了执行效率

具体步骤如下：

1. 统计频率：用一个 map 数组来存储 nums 里每个数的出现次数

2. 构造二维数组：遍历 map，按照元素出现的次数依次填充行。如果当前二维数组的行数不够，就新建一行

3. 返回结果：最终得到符合要求的二维数组

代码实现

class Solution {
    public List<List<Integer>> findMatrix(int[] nums) {
        int[] map = new int[nums.length + 1];
        for (int num : nums) {
            map[num]++;
        }
        List<List<Integer>> ans = new ArrayList<>();
        for (int key = 1; key < map.length; key++) {
            int count = map[key];
            for (int i = 0; i < count; i++) {
                if (ans.size() < count) {
                    ans.add(new ArrayList<>());
                }
                ans.get(i).add(key);
            }
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(n)，我们需要遍历 nums 统计频率，然后再次遍历 map 构造结果数组，总体仍是 O(n)

• 空间复杂度：O(n)，用于存储结果 ans 和元素频率 map

总结

这道题整体来说不难，但在实现过程中，我踩到了遍历 HashMap 时修改集合的坑，后来改用数组存储频率后，代码逻辑更清晰、执行效率也更高。这让我意识到，有时候换个角度思考，能避免很多不必要的问题。

此外，这道题也让我再次体会到灵活使用 List<List<Integer>> 进行动态扩展的必要性，特别是在构造二维数组时，要根据需求动态增加行，确保满足题目要求。

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。