-
Notifications
You must be signed in to change notification settings - Fork 0
/
1282.py
46 lines (32 loc) · 1.3 KB
/
1282.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
# 1282. Group the People Given the Group Size They Belong To
# 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
from typing import List
from collections import defaultdict
class Solution:
def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
result = []
info = defaultdict(list)
for index, value in enumerate(groupSizes):
info[value].append(index)
if len(info[value]) == value:
result.append(info[value])
info[value] = []
return result
if __name__ == "__main__":
s = Solution()
print(s.groupThePeople([3, 3, 3, 3, 3, 1, 3]))