1282. 用户分组(贪心算法)

有 n 位用户参加活动,他们的 ID 从 0 到 n - 1,每位用户都 恰好 属于某一用户组。给你一个长度为 n 的数组 groupSizes,其中包含每位用户所处的用户组的大小,请你返回用户分组情况(存在的用户组以及每个组中用户的 ID)。你可以任何顺序返回解决方案,ID 的顺序也不受限制。此外,题目给出的数据保证至少存在一种解决方案。

示例 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 = [3,3,3,3,3,1,3];
二元组maps=[[3, 0], [3, 1], [3, 2], [3, 3], [3, 4], [1, 5], [3, 6]];
排序后maps=[[1, 5], [3, 0], [3, 1], [3, 2], [3, 3], [3, 4], [3, 6]];
分为三组,大小分别为1,3,3,即grp1=[[1, 5]],grp2=[[3, 0], [3, 1], [3, 2]],grp3=[[3, 3], [3, 4], [3, 6]];
可与第4步合并,给用户分组故无需size,grp1=[5],grp2=[0,1,2],grp3=[3,4,6]。

class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        maps=[[v,k] for k,v in enumerate(groupSizes)]
        maps.sort(key=lambda x:x[0])
        i=0
        res=[]
        while i<len(maps):
            grp=maps[i:i+maps[i][0]]
            i=i+maps[i][0]
            res.append([item[1] for item in grp])
        return res

链接:https://leetcode-cn.com/problems/group-the-people-given-the-group-size-they-belong-to/solution/tong-su-yi-dong-python3-by-hong-chen-11/

原文地址:https://www.cnblogs.com/USTC-ZCC/p/12915173.html