By

前言

Github：https://github.com/HealerJean

博客：http://blog.healerjean.com

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));
    }

​

ContactAuthor