1. 題目

有 n 位用戶參加活動，他們的 ID 從 0 到 n - 1，每位用戶都 恰好 屬于某一用戶組。給你一個(gè)長度為 n 的數(shù)組 groupSizes，其中包含每位用戶所處的用戶組的大小，請你返回用戶分組情況（存在的用戶組以及每個(gè)組中用戶的 ID）。

你可以任何順序返回解決方案，ID 的順序也不受限制。此外，題目給出的數(shù)據(jù)保證至少存在一種解決方案。

示例 1： 輸入：groupSizes = [3,3,3,3,3,1,3] 輸出：[[5],[0,1,2],[3,4,6]] 解釋： 其他可能的解決方案有 [[2,1,6],[5],[0,4,3]] 和 [[5],[0,6,2],[4,3,1]]。示例 2： 輸入：groupSizes = [2,1,3,3,3,2] 輸出：[[1],[0,5],[2,3,4]]提示： groupSizes.length == n 1 <= n <= 500 1 <= groupSizes[i] <= n

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/group-the-people-given-the-group-size-they-belong-to
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. multimap 解題

• 利用 multimap 的有序性，將 <組的長度，ID> 插入map
• 依次將短的組push_back進(jìn)數(shù)組，數(shù)組長度滿了，再開一個(gè)新的數(shù)組

class Solution { public:vector<vector<int>> groupThePeople(vector<int>& groupSizes) {multimap<int,int> m;for(int i = 0; i < groupSizes.size(); ++i)m.emplace(groupSizes[i],i);vector<vector<int>> ans(1);for(auto& kv : m){if(ans.back().size() < kv.first)ans.back().push_back(kv.second);if(ans.back().size() == kv.first)ans.push_back({});}if(ans.back().size() == 0)ans.pop_back();return ans;} };

or

桶排序思想，將長度相同的放到一個(gè)桶里，桶滿了，push進(jìn)答案，清空桶

class Solution { public:vector<vector<int>> groupThePeople(vector<int>& groupSizes) {vector<vector<int>> temp(500);vector<vector<int>> ans;for(int i = 0; i < groupSizes.size(); ++i){temp[groupSizes[i]].push_back(i);if(temp[groupSizes[i]].size() == groupSizes[i]){ans.push_back(temp[groupSizes[i]]);temp[groupSizes[i]].clear();}}return ans;} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1282. 用户分组（桶排序思想）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。