There are n
people whose IDs go from 0
to n - 1
and each person belongs exactly to one group. Given the array groupSizes
of length n
telling the group size each person belongs to, return the groups there are and the people’s IDs each group includes.
You can return any solution in any order and the same applies for IDs. Also, it is guaranteed that there exists at least one solution.
Example 1:
Input: groupSizes = [3,3,3,3,3,1,3] Output: [[5],[0,1,2],[3,4,6]] Explanation: 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 == n
1 <= n <= 500
1 <= groupSizes[i] <= n
Solution: HashMap + Greedy
hashmap: group_size -> {ids}
greedy: whenever a group of size s has s people, assign those s people to the same group.
Time complexity: O(n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua class Solution { public: vector<vector<int>> groupThePeople(vector<int>& groupSizes) { vector<vector<int>> ans; const int n = groupSizes.size(); unordered_map<int, vector<int>> m; for (int i = 0; i < n; ++i) { auto& v = m[groupSizes[i]]; v.push_back(i); if (v.size() == groupSizes[i]) ans.push_back(std::move(v)); } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment