今日算法之_70_用户分组
前言
Github:https://github.com/HealerJean
1、用户分组
有 n 位用户参加活动,他们的 ID 从 0 到 n - 1,每位用户都 恰好 属于某一用户组。给你一个长度为 n 的数组 groupSizes,其中包含每位用户所处的用户组的大小,请你返回用户分组情况(存在的用户组以及每个组中用户的 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]]
1.1、解题思路
利用map,元素作为key存入,value 元素的下标集合, 遍历一次数组,如果key存在,value集合+1,知道value的的集合大小等于key的值,那么这组就成立了。然后将这个key移除,继续走走数组
遇到key为1的情况,就表示只有它一个人是一组。
1.2、算法
public List<List<Integer>> groupThePeople(int[] groupSizes) {
List<List<Integer>> list = new ArrayList<>();
Map<Integer, List<Integer>> map = new HashMap<>();
for(int i = 0 ; i < groupSizes.length ; i++){
if (map.containsKey(groupSizes[i])){
List<Integer> group = map.get(groupSizes[i]);
group.add(i);
if(groupSizes[i] == group.size()){
list.add(group);
map.remove(groupSizes[i]);
}
}else {
if (groupSizes[i] == 1 ){
list.add(Arrays.asList(i));
}else {
List<Integer> group = new ArrayList<>();
group.add(i);
map.put(groupSizes[i] , group);
}
}
}
return list ;
}
1.3、测试
@Test
public void test(){
int[] groupSizes = {2, 2, 1, 1, 1, 1, 1, 1};
System.out.println(groupThePeople(groupSizes));
}