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 1

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

class Solution {
public:
    vectorvectorint>> findMatrix(vecto服务器托管网rint>& nums) {
        unordered_mapint, int> numToRemainNum;
        for (int num : nums)
        {
            ++numToRemainNum[num];
        }

        vectorvectorint>> 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:
    vectorvectorint>> findMatrix(vectorint>& nums) {
       服务器托管网 unordered_mapint, int> positionArr;
        vectorvectorint>> 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;
    }
};

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

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: Django模型（一）

一、介绍 模型，就是python中的类对应数据库中的表 1.1、ORM ORM 就是通过实例对象的语法，完成关系型数据库的操服务器托管网作的技术，是”对象-关系映射”（Object/服务器托管网Relational Mapping） 的缩写 ORM 把数据库映…