---
# System prepended metadata

title: Leetcode 2610 Convert an Array Into a 2D Array With Conditions
tags: [Leetcode, 程式菜雞的coding日常]

---

# Leetcode 2610 Convert an Array Into a 2D Array With Conditions
###### tags: `Leetcode` `程式菜雞的coding日常` 
## 題目原文
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.

## 題目理解
題目會給一個一維陣列，要在滿足以下三個條件的同時把他轉為二維陣列，然後回傳運算完的二維陣列。條件分別是
- 這個二維陣列的元素必須是`nums`裡有的
- 這個二維陣列的每一個row裡的元素都是相異的
- 二維陣列的row數必須為最少

其中每個row的元素數量可以不同，如果有多個答案，則回傳任意一個即可。

## 解題思路
由於要求row數需為最少，且每個row不能有重複的元素，那就將出現最多次的數字的次數作為總row數。
首先建一個map紀錄每個數字出現的次數，然後遍歷整個map就好。

以範例測資[1,3,4,1,2,3,1]為例。
其中1出現次數最多，為3次，因此轉換後的row數為3。
其餘數字為2出現1次，3出現2次，4出現1次。
因此將1丟到3個row裡面，2丟一個，3丟2個，以此類推。
理論上可以隨機丟，但是為了程式撰寫方便，我選擇能丟在最前面就丟最前面。
此外，因為map會自動排序，所以我的輸出跟範例輸出不太一樣，用下面的程式跑出來的輸出會是[[1,2,3,4],[1,3],[1]]，但答案一樣是對的。


## 程式實作
```cpp=
class Solution {
public:
    vector<vector<int>> findMatrix(vector<int>& nums) {
        int n = nums.size();
        map<int,int> count;
        for(int i = 0; i < n ; i++){
            count[nums[i]]++;
        }
        
        vector<vector<int>> ans;
        map<int,int>::iterator it;
        for(it = count.begin() ; it != count.end() ; it++){
            if(ans.size() < it->second) ans.resize(it->second);
            for(int i = 0 ; i < it->second ; i++){
                ans[i].push_back(it->first);
            }
        }
        return ans;
    }
};
```

## 後記
我有時候解過題一陣子之後回去看同一題，會完全看不懂那時候的自己在寫三小東西，現在可以用這個紀錄真是幫大忙了 ~~(羅文笑.jpg)~~
