2610.转换二维数组:哈希表(一次遍历)

【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加入ans[1]中。

  • 时间复杂度O(len(nums))
  • 空间复杂度O(len(nums))

AC代码

C++

1
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:54:08
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-03-19 19:55:17
*/
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

Python

1
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 defaultdict


class 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

Java

1
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
/*
* @Author: LetMeFly
* @Date: 2025-03-19 19:58:16
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-03-19 20:03:10
*/
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

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
* @Author: LetMeFly
* @Date: 2025-03-19 20:03:37
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-03-19 20:05:02
*/
package main

func 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和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~

千篇源码题解已开源


2610.转换二维数组:哈希表(一次遍历)
https://blog.letmefly.xyz/2025/03/19/LeetCode 2610.转换二维数组/
作者
发布于
2025年3月19日
许可协议