难度: Medium
给你一个整数数组 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 <= 2001 <= nums[i] <= nums.length运行时间: 32 ms
内存: 16.1 MB
from typing import List
from collections import Counter
class Solution:
def findMatrix(self, nums: List[int]) -> List[List[int]]:
counter = Counter(nums)
max_count = max(counter.values())
rows = [[] for _ in range(max_count)]
for num in nums:
count = counter[num]
for i in range(count):
rows[i].append(num)
if len(rows[i]) == len(counter):
break
return [list(set(row)) for row in rows]
from typing import List
class Solution:
def findMatrix(self, nums: List[int]) -> List[List[int]]:
counter = {}
for num in nums:
counter[num] = counter.get(num, 0) + 1
rows = []
for num in nums:
if counter[num] > 0:
placed = False
for row in rows:
if num not in row:
row.append(num)
counter[num] -= 1
placed = True
break
if not placed:
rows.append([num])
counter[num] -= 1
return rows
此题解主要利用了哈希表来记录每个数字出现的次数，并通过构造多个行数组来保证每一行的数字都是不同的。首先，使用Counter或字典统计每个数字出现的次数。然后，基于数字出现的次数，为每个数字在不同的行中分配位置。如果一个数字出现n次，则它将尝试放在前n行中的每一行。这样，可以确保二维数组的行数尽可能少，并且每一行的数字都是不同的。
时间复杂度: O(n*m)
空间复杂度: O(n + u)
from typing import List
from collections import Counter
class Solution:
def findMatrix(self, nums: List[int]) -> List[List[int]]:
counter = Counter(nums) # 创建数字计数器
max_count = max(counter.values()) # 找到最多次数的数字的出现频率
rows = [[] for _ in range(max_count)] # 根据最大次数创建行数组
for num in nums: # 遍历每个数字
count = counter[num] # 获取数字出现次数
for i in range(count): # 将数字放入不同的行中
rows[i].append(num)
if len(rows[i]) == len(counter): # 如果行的长度达到计数器长度，停止添加
break
return [list(set(row)) for row in rows] # 返回处理后的行，确保每行数字不重复
class Solution:
def findMatrix(self, nums: List[int]) -> List[List[int]]:
counter = {} # 使用字典存储数字的出现次数
for num in nums: # 统计每个数字的出现次数
counter[num] = counter.get(num, 0) + 1
rows = [] # 初始化行列表
for num in nums: # 再次遍历数字，进行放置
if counter[num] > 0: # 如果数字仍有剩余
placed = False
for row in rows: # 尝试放入现有行
if num not in row: # 如果行中尚未有此数字
row.append(num)
counter[num] -= 1 # 减少数字剩余计数
placed = True
break
if not placed: # 如果没有合适的行，则新开一行
rows.append([num])
counter[num] -= 1
return rows # 返回结果二维数组
哈希表（例如 Python 中的字典或 Counter）在算法中用于记录每个数字的出现次数，因为它可以在常数时间内完成插入和查找操作，这使得统计每个元素的频率变得非常高效。此外，哈希表还可以方便地访问任何具体数字的计数，这对于后续的数字分配和检查是否已将某数字放入特定行中非常关键。
算法通过在放置数字之前检查该数字是否已存在于当前行来确保每行中的数字都是唯一的。在第一种解法中，每个数字尝试按其出现次数顺序被添加到不同的行中，行中已有数字会使用集合来去重。在第二种解法中，通过在添加前检查行中是否已包含该数字来直接防止重复。如果行中已存在该数字，则搜索下一行或创建新行。
当数字的出现次数非常高时，算法的性能确实会受到影响。首先，需要更多的行来放置重复频次高的数字，这增加了行数组的大小和处理时间。其次，特别是在第二种解法中，每次放置数字时都需要检查多行以确认数字是否已存在，这会导致更多的行检查操作，从而增加时间复杂度。因此，数字频次的增加直接影响到行的管理和搜索时间，尤其是在行数较多时。
在处理数字时，需要检查并尝试将数字放置在已有的所有行中，以确保不违反每行数字唯一性的约束。这种方法虽然可行，但不是最高效的。一个更高效的方法可能是使用额外的数据结构，如哈希表或位图，来追踪每行已经包含哪些数字。这样，可以在常数时间内检查数字是否已在行中，从而减少不必要的行检查。另外，维护一个指针数组，指向每行的下一个可放置位置，也可以提高效率，避免每次都从头扫描每行。