LeetCode 2610.转换二维数组

本文主要是介绍LeetCode 2610.转换二维数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

法一：将nums中的每个数字放入哈希表，值为该数字的未使用次数，然后每次循环对哈希表中还未使用的数字放入一个答案数组：

class Solution {
public:vector<vector<int>> findMatrix(vector<int>& nums) {unordered_map<int, int> numToRemainNum;for (int num : nums){++numToRemainNum[num];}vector<vector<int>> ans;while (!numToRemainNum.empty()){ans.push_back({});for (auto it = numToRemainNum.begin(); it != numToRemainNum.end(); ){ans.back().push_back(it->first);if (--it->second == 0){it = numToRemainNum.erase(it);}else{++it;}}}return ans;}
};

如果nums的长度为n，则此算法时间复杂度为O(n)，空间复杂度为O(n)。

法二：用一个数组存每个数组当前应该存放到的数组下标，然后遍历nums中的每个数字，将该数字放到对应下标的数组中：

class Solution {
public:vector<vector<int>> findMatrix(vector<int>& nums) {unordered_map<int, int> positionArr;vector<vector<int>> ans;for (int num : nums){int position = positionArr[num];++positionArr[num];if (position >= ans.size()){ans.push_back({});}ans[position].push_back(num);}return ans;}
};