【八月】每日一题 - 1282. 用户分组

简介: 【八月】每日一题 - 1282. 用户分组

问题描述

有 n 个人被分成数量未知的组。每个人都被标记为一个从 0 到 n - 1 的唯一ID 。

给定一个整数数组 groupSizes ,其中 groupSizes[i] 是第 i 个人所在的组的大小。例如,如果 groupSizes[1] = 3 ,则第 1 个人必须位于大小为 3 的组中。

返回一个组列表,使每个人 i 都在一个大小为 groupSizes[i] 的组中。

每个人应该 恰好只 出现在 一个组 中,并且每个人必须在一个组中。如果有多个答案,返回其中 任何 一个。可以 保证 给定输入 至少有一个 有效的解。

示例 1:

输入:groupSizes = [3,3,3,3,3,1,3]
输出:[[5],[0,1,2],[3,4,6]]
解释:
第一组是 [5],大小为 1,groupSizes[5] = 1。
第二组是 [0,1,2],大小为 3,groupSizes[0] = groupSizes[1] = groupSizes[2] = 3。
第三组是 [3,4,6],大小为 3,groupSizes[3] = groupSizes[4] = groupSizes[6] = 3。 
其他可能的解决方案有 [[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.cn/problems/gr…

解题思路

在本题中,groupSizes[i] 代表第 i 个人所在的组的大小,处于同一个组的人,groupSizes[i]一定相同,我们只需要通过Map来记录不同的Size,以及该Size内的人(下标)。

同时需要注意以下一点

  • 当一个组满员的时候,该组就添加到结果中,并且Map重制该大小的组

AC代码

var groupThePeople = function(groupSizes) {
    const result = []
    const map = new Map()
    for(let i = 0; i < groupSizes.length; i++){
        if(!map.get(groupSizes[i])){ // 不存在该组 或者已经被置空
            if(groupSizes[i] === 1){ // 一个人为一组则直接推入结果集
                result.push([i])
            }else{
                map.set(groupSizes[i],[i])
            }
        }else{
            // 当前这个人加入该组的时候恰好满员,则推入结果并且置空该组
            if(map.get(groupSizes[i]).length === groupSizes[i] - 1){ 
                result.push([...map.get(groupSizes[i]),i])
                map.set(groupSizes[i],false)
            }else{
                map.set(groupSizes[i],[...map.get(groupSizes[i]),i])
            }
        }
    }
    return result
};


目录
打赏
0
0
0
0
2
分享
相关文章
【每日一题Day365】LC2172参加会议的最多员工数 | 拓扑排序
【每日一题Day365】LC2172参加会议的最多员工数 | 拓扑排序
99 1
考研真题)某银行提供了 1 个服务窗口和 10 个供顾客等待时使用的座位。顾客到达银行时,若有空座位,则到取号机上领取一个号,等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时,通过叫号选取一位顾
考研真题)某银行提供了 1 个服务窗口和 10 个供顾客等待时使用的座位。顾客到达银行时,若有空座位,则到取号机上领取一个号,等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时,通过叫号选取一位顾
深入解析力扣181题:超过经理收入的员工(自连接方法详解及模拟面试问答)
深入解析力扣181题:超过经理收入的员工(自连接方法详解及模拟面试问答)
蓝桥备战--纪念品分组OJ532,贪心证明
蓝桥备战--纪念品分组OJ532,贪心证明
47 0
【蓝桥杯省赛】冲刺练习题【经典题目练习】倒计时【01】天(准考证组委会已下发,请查询)-1
【蓝桥杯省赛】冲刺练习题【经典题目练习】倒计时【01】天(准考证组委会已下发,请查询)
142 0
【蓝桥杯省赛】冲刺练习题【经典题目练习】倒计时【01】天(准考证组委会已下发,请查询)-1
PAT-2021年秋季考试 乙级 7-3 自定义判题程序 (20 分)
在每次允许插入、删除、修改一个字符的前提下,用最少的动作把一个字符串变成另一个字符串,是一道著名的可以用动态规划解决的问题。
189 0
L1-038 新世界 (5 分)
L1-038 新世界 (5 分)
115 0
093.波瓦松的分酒趣题
093.波瓦松的分酒趣题
125 0
7-35 部落 (10 分)
7-35 部落 (10 分)
90 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等