Last Updated on 2023-09-11 by Clay
There are n people that are split into some unknown number of groups. Each person is labeled with a unique ID from 0 to n - 1.
You are given an integer array groupSizes, where groupSizes[i] is the size of the group that person i is in. For example, if groupSizes[1] = 3, then person 1 must be in a group of size 3.
Return a list of groups such that each person i is in a group of size groupSizes[i].
Each person should appear in exactly one group, and every person must be in a group. If there are multiple answers, return any of them. It is guaranteed that there will be at least one valid solution for the given input.
Example 1:Input: groupSizes = [3,3,3,3,3,1,3] Output: [[5],[0,1,2],[3,4,6]] Explanation: The first group is [5]. The size is 1, and groupSizes[5] = 1. The second group is [0,1,2]. The size is 3, and groupSizes[0] = groupSizes[1] = groupSizes[2] = 3. The third group is [3,4,6]. The size is 3, and groupSizes[3] = groupSizes[4] = groupSizes[6] = 3. Other possible solutions are [[2,1,6],[5],[0,4,3]] and [[5],[0,6,2],[4,3,1]].
Example 2:Input: groupSizes = [2,1,3,3,3,2] Output: [[1],[0,5],[2,3,4]]
Constraints:
groupSizes.length == n1 <= n <= 5001 <= groupSizes[i] <= n
簡單來說，題目給定的 groupSizes 裡面的每一個值，代表著『應該被歸類到多少數量的陣列中』，而在歸類到的陣列中，應該用索引（index）儲存著。
解題思路
這題我是直接暴力法，用 hash 來讓『應該建立的陣列長度』對應到『陣列群集』中，然後在讀取到輸入陣列的數值時，直接匹配到對應長度的陣列中。
比方說我的第一個值是 3，我就建立一個 3 => arr(arr()) 的對應，然後把 index=0 放在裡頭。依此類推，如果陣列即將大於 3 ，就再新增另外一個陣列放在數值 3 對應的 mapping 表中。
C++ 範例程式碼
class Solution {
public:
vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
// Init
int maxSize = 0;
vector<vector<int>> results;
unordered_map<int, vector<vector<int>>> idx2groupArr;
// Split
for (int i=0; i<groupSizes.size(); ++i) {
int currSize = groupSizes[i];
maxSize = max(maxSize, currSize);
bool fit = false;
for (vector<int>& arr: idx2groupArr[currSize]) {
if (arr.size() < currSize) {
arr.emplace_back(i);
fit = true;
break;
}
}
if (!fit) {
vector<int> newArr({i});
idx2groupArr[currSize].emplace_back(newArr);
}
}
// Format
for (int size=1; size<=maxSize; ++size) {
for (vector<int>& arr: idx2groupArr[size]) {
results.emplace_back(arr);
}
}
return results;
}
};Python 範例程式碼
class Solution:
def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
# Init
max_size = 0
results = []
idx2arr = {}
# Split
for i in range(len(groupSizes)):
curr_size = groupSizes[i]
max_size = max(max_size, curr_size)
fit = False
if curr_size not in idx2arr:
idx2arr[curr_size] = [[i]]
continue
for arr in idx2arr[curr_size]:
if len(arr) < curr_size:
arr.append(i)
fit = True
break
if not fit:
idx2arr[curr_size].append([i])
# Format
for size in range(1, max_size+1):
if size not in idx2arr:
continue
for arr in idx2arr[size]:
results.append(arr)
return results