M-1282. Group the People Given the Group Size They Belong To

Group the People Given the Group Size They Belong To - LeetCodeLeetCode

# 自己的方法 O(n), O(n)
from collections import defaultdict
class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        group_map = defaultdict(list)
        group_ids = [0]*len(groupSizes)
        for i, group_size in enumerate(groupSizes):
            if len(group_map[(group_size, group_ids[group_size-1])]) >= group_size:
                group_ids[group_size-1] += 1
            group_map[(group_size,group_ids[group_size-1])].append(i)
        res = [group for group in group_map.values()]
        return res

# 网友方法, 先还是把同数量的组的id放到一个list里，然后再用这个数量去均分这个list：
from collections import defaultdict
class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        group_map = defaultdict(list)
        for i, size in enumerate(groupSizes):
            group_map[size].append(i)
        res = []
        for size, group_with_same_size in group_map.items():
            for i in range(0, len(group_with_same_size), size):
                res.append(group_with_same_size[i:i+size])
        return res

# 网友原来的答案
class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        '''
		Example input-> groupSizes=[3,3,3,3,3,1,3]
        Store in a dictionary[i] the list of indices of input array groupSizes that belong to a group size i 
		'''
        group_map = collections.defaultdict(list)
        for idx,i in enumerate(groupSizes):
            group_map[i].append(idx)
        '''
        print (group_map )-> defaultdict(<class 'list'>, {3: [0, 1, 2, 3, 4, 6], 1: [5]})
        group_map[i] has list of indices of input array groupSizes that belong to groupsize i
        Next, create lists of size i parsing through group_map[i], and append them to answer[].
        Further since a solution is guaranteed to exist, len(group_map[i])/i will always be perfectly divisible. 
		Infact, len(group_map[i])/i gives exactly the number of groups of size i
        '''
        answer=[]
        for key, lst in group_map.items():
            for idx in range(0, len(lst), key):
                answer.append(lst[idx:idx + key])
        return (answer)