转换二维数组
难度:
标签:
题目描述
You are given an integer array nums. You need to create a 2D array from nums satisfying the following conditions:
- The 2D array should contain only the elements of the array
nums. - Each row in the 2D array contains distinct integers.
- The number of rows in the 2D array should be minimal.
Return the resulting array. If there are multiple answers, return any of them.
Note that the 2D array can have a different number of elements on each row.
Example 1:
Input: nums = [1,3,4,1,2,3,1] Output: [[1,3,4,2],[1,3],[1]] Explanation: We can create a 2D array that contains the following rows: - 1,3,4,2 - 1,3 - 1 All elements of nums were used, and each row of the 2D array contains distinct integers, so it is a valid answer. It can be shown that we cannot have less than 3 rows in a valid array.
Example 2:
Input: nums = [1,2,3,4] Output: [[4,3,2,1]] Explanation: All elements of the array are distinct, so we can keep all of them in the first row of the 2D array.
Constraints:
1 <= nums.length <= 2001 <= nums[i] <= nums.length
代码结果
运行时间: 32 ms, 内存: 16.1 MB
/*
* 思路：
* 1. 使用流的特性来简化代码。
* 2. 首先将数组转换为Set集合，去重并生成第一个结果行。
* 3. 通过移除已处理的元素，继续生成剩余的行。
*/
import java.util.*;
import java.util.stream.Collectors;
public class Solution {
public List<List<Integer>> findMatrix(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Set<Integer> used = Arrays.stream(nums).boxed().collect(Collectors.toSet());
while (!used.isEmpty()) {
Set<Integer> rowSet = new HashSet<>();
List<Integer> row = Arrays.stream(nums)
.boxed()
.filter(num -> used.contains(num) && rowSet.add(num))
.collect(Collectors.toList());
result.add(row);
row.forEach(used::remove);
}
return result;
}
}
解释
方法:
此题解主要利用了哈希表来记录每个数字出现的次数，并通过构造多个行数组来保证每一行的数字都是不同的。首先，使用Counter或字典统计每个数字出现的次数。然后，基于数字出现的次数，为每个数字在不同的行中分配位置。如果一个数字出现n次，则它将尝试放在前n行中的每一行。这样，可以确保二维数组的行数尽可能少，并且每一行的数字都是不同的。
时间复杂度:
O(n*m)
空间复杂度:
O(n + u)
代码细节讲解
🦆
在算法中，为什么首先选择使用哈希表来记录每个数字的出现次数？
▷🦆
算法是如何确保每一行中的数字都是唯一的？
▷🦆
当数字的出现次数非常高时，算法的性能是否会受到影响？如果会，为什么？
▷🦆
在处理数字时，为什么需要检查并尝试将数字放置在已有的所有行中？是否有更高效的方法来避免反复的行检查？
▷