题目描述

有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]]

解题思路

这道题可以先做排序，对排序后结果进行分组：

• 准备一个数组，array[][]，分别记录groupSize和下标；
• 按照groupSize对array进行排序；
• 准备一个List> res，第一次或者是list.size()==groupSize则创建一个新的list。

代码实现如下：

 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
 
class Solution2 {
    public List> groupThePeople(int[] groupSizes) {
 
        int[][] array = new int[groupSizes.length][2];
 
 
        for (int i = 0; i < groupSizes.length; i++) {
            array[i][0] = groupSizes[i];
            array[i][1] = i;
        }
 
        Arrays.sort(array, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
 
        ArrayList> res = new ArrayList<>(groupSizes.length);
        res.add(new ArrayList<>());
 
        for (int i = 0; i < array.length; i++) {
            int[] v = array[i];
            int size = v[0];
            int index = v[1];
 
            List list = res.get(res.size() - 1);
            list.add(index);
 
            if (i >= array.length - 1) {
                break;
            }
 
            if (size <= list.size()) {
                res.add(new ArrayList<>());
            }
        }
 
        return res;
    }
 
    public static void main(String[] args) {
        Solution2 solution = new Solution2();
        System.out.println(solution.groupThePeople(new int[]{3, 3, 3, 3, 3, 1, 3}));
    }
}

---

上述这种实现方式耗时上不是最优的，排序就需要O(N*LogN)。

为了降低时间复杂度，我不再进行排序，切换使用MAP来解决问题，为了最大化降低时间复杂度，自己实现了一个简单的哈希表：

 
    class MyMap {
        final List[] array;
 
        public MyMap(int length) {
            this.array = new List[length + 1];
        }
 
        public List get(int key) {
            return this.array[key];
        }
 
        public void put(int key, List list) {
            this.array[key] = list;
        }
    }

基于哈希表的解题思路：

• 遍历数组，获取groupSize和下标i；
• 从哈希表中获取groupSize对应的List，如果List为空则新建，如果List不为空则添加下标i
• 判断List的大小是不是大于等于groupSize，如果大于等于则重新创建List；

按照上述思路代码实现：

 
import java.util.ArrayList;
import java.util.List;
 
class Solution4 {
    public List> groupThePeople(int[] groupSizes) {
        MyMap map = new MyMap(groupSizes.length);
        List> res = new ArrayList<>();
 
        for (int i = 0; i < groupSizes.length; i++) {
            int groupSize = groupSizes[i];
            List list = map.get(groupSize);
            if (list == null) {
                map.put(groupSize, list = new ArrayList<>(groupSize));
            }
            list.add(i);
 
            if (list.size() >= groupSize) {
                res.add(list);
                map.put(groupSize, new ArrayList<>(groupSize));
            }
        }
        return res;
    }
 
    class MyMap {
        final List[] array;
 
        public MyMap(int length) {
            this.array = new List[length + 1];
        }
 
        public List get(int key) {
            return this.array[key];
        }
 
        public void put(int key, List list) {
            this.array[key] = list;
        }
    }
 
    public static void main(String[] args) {
        Solution4 solution = new Solution4();
        System.out.println(solution.groupThePeople(new int[]{3, 3, 3, 3, 3, 1, 3}));
    }
}

总结

这道题在解答思路上要注意一下，一定要用通过哈希表来做，因为排序耗时和哈希表操作的时间复杂度差别很大；

上述代码哈希表，还可以进一步改写，直接使用局部变量数组来做，时间上还能有所下降，但是均无法到达最快耗时，欢迎大家提供更快更好的思路。