【八月】每日一题 - 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
分享
相关文章
11.Java方法的综合练习题大全-双色球彩票系统,数字的加密和解密等试题(下)
11.Java方法的综合练习题大全-双色球彩票系统,数字的加密和解密等试题(上)
132 1
深入解析力扣181题:超过经理收入的员工(自连接方法详解及模拟面试问答)
深入解析力扣181题:超过经理收入的员工(自连接方法详解及模拟面试问答)
蓝桥青少年组——计算24 2020-11-25
蓝桥青少年组——计算24 2020-11-25
☆打卡算法☆LeetCode 181. 超过经理收入的员工 算法解析
☆打卡算法☆LeetCode 181. 超过经理收入的员工 算法解析
|
9月前
蓝桥备战--纪念品分组OJ532,贪心证明
蓝桥备战--纪念品分组OJ532,贪心证明
35 0
|
9月前
|
C++
第十三届蓝桥杯B组C++(试题B:顺子日期)
第十三届蓝桥杯B组C++(试题B:顺子日期)
98 0
第十二届蓝桥杯省赛第二场 C++ B组 - 特殊年份
第十二届蓝桥杯省赛第二场 C++ B组 - 特殊年份
125 0
第十二届蓝桥杯省赛 C++ B组 - 时间显示
第十二届蓝桥杯省赛 C++ B组 - 时间显示
94 0