無盡算法之用戶編組

有 n 位用戶參加活動(dòng)，他們的 ID 從 0 到 n - 1，每位用戶都 恰好 屬于某一用戶組。給你一個(gè)長(zhǎng)度為 n 的數(shù)組 groupSizes，其中包含每位用戶所處的用戶組的大小，請(qǐng)你返回用戶分組情況（存在的用戶組以及每個(gè)組中用戶的 ID）。

?

你可以任何順序返回解決方案，ID 的順序也不受限制。此外，題目給出的數(shù)據(jù)保證至少存在一種解決方案。

?

示例 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 ] ]

?

提示：

groupSizes.length == n

1 <= n <= 500

1 <= groupSizes[i] <= n

?

思路：

使用Hashmap

以groupSize為key, 以ArrayList(ArrayList())為value, 這里存放的Integer就是userId(也就是數(shù)組index)

插入策略：

先判斷是否有key，無key則直接生成新的ArrayList(ArrayList())， 并且添加一個(gè)子ArrayList, 同時(shí)插入userId

有key再判斷取出的ArrayList內(nèi)部的最后一個(gè)ArrayList長(zhǎng)度是否等于對(duì)應(yīng)的groupSize， 如果相等， 則追加到新組， 否則追加

題解：

public class Test {

????public static void main(String[] args) {

????????System.out.println(groupThePeople(new int[]{3,3,3,3,1,3,3}));

????}

?

????private static HashMap<Integer, ArrayList> resultMap = new HashMap<>();

?

????public static List<List<Integer>> groupThePeople(int[] groupSizes) {

????????ArrayList<List<Integer>> results = new ArrayList<>();

????function(){ //點(diǎn)差?http://www.kaifx.cn/question/kaifx/1799.html

????????for (int i=0;i<groupSizes.length;i++) {

????????????add(i,groupSizes[i]);

????????}

????????for (ArrayList i : resultMap.values()) {

????????????results.addAll(i);

????????}

????????return results;

????}

?

????static void ?add(int id, int groupSize) {

????????if (resultMap.get(groupSize) == null) {

????????????ArrayList<List<Integer>> groupList = new ArrayList<>();

????????????List<Integer> group=new ArrayList<>();

????????????group.add(id);

????????????groupList.add(group);

????????????resultMap.put(groupSize, groupList);

????????} else {

????????????ArrayList<List<Integer>> a = resultMap.get(groupSize);

????????????if (a.get(a.size() - 1).size() == groupSize ) {

????????????????List<Integer> group=new ArrayList<>();

????????????????group.add(id);

????????????????a.add(group);

????????????} else {

????????????????a.get(a.size() - 1).add(id);

????????????}

????????}

????}

}

?