【LetMeFly】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 中的所有元素都有用到,并且每一行都由不同的整数组成,所以这是一个符合题目要求的答案。
可以证明无法创建少于三行且符合题目要求的二维数组。 TEXT
示例 2:
输入: nums = [1,2,3,4]
输出: [[4,3,2,1]]
解释: nums 中的所有元素都不同,所以我们可以将其全部保存在二维数组中的第一行。
TEXT
提示:
1 <= nums.length <= 200
1 <= nums[i] <= nums.length
解题方法:哈希表使用一个哈希表统计每个数出现的次数。
遍历nums数组,统计当前元素的出现次数。若当前元素的出现次数大于答案数组的长度,就向答案数组中添加一个空数组。最后,将当前元素t加入中。
AC代码 C++1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution {public : vector<vector<int >> findMatrix (vector<int >& nums) { vector<vector<int >> ans; unordered_map<int , int > cnt; for (int t : nums) { cnt[t]++; if (cnt[t] > ans.size ()) { ans.push_back ({}); } ans[cnt[t] - 1 ].push_back (t); } return ans; } };
CPP
Python1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 ''' Author: LetMeFly Date: 2025-03-19 19:56:03 LastEditors: LetMeFly.xyz LastEditTime: 2025-03-19 19:57:12 ''' from typing import List from collections import defaultdictclass Solution : def findMatrix (self, nums: List [int ] ) -> List [List [int ]]: ans: List [List [int ]] = [] ma = defaultdict(int ) for t in nums: ma[t] += 1 if ma[t] > len (ans): ans.append([]) ans[ma[t] - 1 ].append(t) return ans
PYTHON
Java1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 import java.util.HashMap;import java.util.Map;import java.util.ArrayList;import java.util.List;class Solution { public List<List<Integer>> findMatrix (int [] nums) { List<List<Integer>> ans = new ArrayList <>(); Map<Integer, Integer> ma = new HashMap <>(); for (int t : nums) { ma.merge(t, 1 , Integer::sum); if (ma.get(t) > ans.size()) { ans.add(new ArrayList <>()); } ans.get(ma.get(t) - 1 ).add(t); } return ans; } }
JAVA
Go1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 package mainfunc findMatrix (nums []int ) (ans [][]int ) { ma := map [int ]int {} for _, t := range nums { ma[t]++ if ma[t] > len (ans) { ans = append (ans, make ([]int , 0 )) } ans[ma[t] - 1 ] = append (ans[ma[t]-1 ], t) } return }
GO
同步发文于CSDN 和我的个人博客 ,原创不易,转载经作者同意后请附上原文链接 哦~
千篇源码题解已开源