LeetCode.1282. 用户分组

LeetCode.1282. 用户分组

难度：medium

 

首先利用哈希表分类信息，对groupSizes的元素进行分类，将值一样的下表存放在List属性的value里，key为要求的组的大小；然后进行分组存储，list满了就再新建一个进行存储即可。

 Java：

class Solution {
    public List> groupThePeople(int[] groupSizes) {
        List> list = new ArrayList>();
        
        Map> map = new HashMap>();
        for (int i = 0; i < groupSizes.length; i++) {
            if (map.containsKey(groupSizes[i])) {
                map.get(groupSizes[i]).add(i);
            } else {
                List temList = new ArrayList<>();
                temList.add(i);
                map.put(groupSizes[i], temList);
            }
        }
 
        for (int i: map.keySet()) {
            List subList = new ArrayList<>();
            for(int j: map.get(i)) {
                subList.add(j);
                if (subList.size() == i) {
                    list.add(subList);
                    subList = new ArrayList<>();
                }
            }
        }
 
        return list;
    }
}

使用getOrDefault方法简化：

class Solution {
    public List> groupThePeople(int[] groupSizes) {
        List> list = new ArrayList>();
        
        Map> map = new HashMap>();
        for (int i = 0; i < groupSizes.length; i++) {
            List list2 = map.getOrDefault(groupSizes[i], new ArrayList<>());
            list2.add(i);
            map.put(groupSizes[i], list2);
        }
 
        for (int i: map.keySet()) {
            List subList = new ArrayList<>();
            for(int j: map.get(i)) {
                subList.add(j);
                if (subList.size() == i) {
                    list.add(subList);
                    subList = new ArrayList<>();
                }
            }
        }
 
        return list;
    }
}

空间复杂度：O（n），哈希表存储了n个元素

时间复杂度：O（n），每个元素都被访问了一遍