Leetcode_1282_Group the People Given the Group Size They Belong To

[lihe]

Group the People Given the Group Size They Belong To

There are n people whose IDs go from 0 to n - 1 and each person belongs exactly to one group. Given the array groupSizes of length n telling the group size each person belongs to, return the groups there are and the people's IDs each group includes.

You can return any solution in any order and the same applies for IDs. Also, it is guaranteed that there exists at least one solution.

Example 1:

Input: groupSizes = [3,3,3,3,3,1,3]
Output: [[5],[0,1,2],[3,4,6]]
Explanation: 
Other possible solutions are [[2,1,6],[5],[0,4,3]] and [[5],[0,6,2],[4,3,1]].

Example 2:

Input: groupSizes = [2,1,3,3,3,2]
Output: [[1],[0,5],[2,3,4]]

Constraints:

• groupSizes.length == n
• 1 <= n <= 500
• 1 <= groupSizes[i] <= n

算法思路：

• 用Map<Integer, List<Integer>>暂存每一个组，循环判断数组中的每一个元素，根据元素的值加入相应的map中，如果组的大小等于key的值，则将map加入result中，清空map。

class Solution{
    public List<List<Integer>> groupThePeople(int[] groupSizes){
        Map<Integer, List<Integer>> map = new HashMap<>();
        List<List<Integer>> result = new ArrayList<>();
        
        for(int i = 0; i < groupSizes.length; i++){
            int flag = groupSizes[i];
            if(! map.containsKey(flag))
                map.put(flag, new ArrayList<>());
            
            map.get(flag).add(i);
            
            if(map.get(flag).size() == flag){
                result.add(map.get(flag));
                map.remove(flag);
            }
        }
        return result;
    }
}