hash数组法长度不固定：集合

前言

在对问题采取hash数组的方法解决的时候，我们往往需要获取问题共性的数组长度，比如说26个字母为26长度，那么如果这个关键词（26个字母中的任意一个）不固定长度（26）呢？我们可以采取集合的方式——不固定长度的特性，使用Map的话，我们称之为字典。list也是可以的。以Leetcode. 1282题为例。

题目

1282. 用户分组

有 n 位用户参加活动，他们的 ID 从 0 到 n - 1，每位用户都 恰好 属于某一用户组。给你一个长度为 n 的数组 groupSizes，其中包含每位用户所处的用户组的大小，请你返回用户分组情况（存在的用户组以及每个组中用户的 ID）。

你可以任何顺序返回解决方案，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]]

解题思路

核心在于：你可以任何顺序返回解决方案，ID 的顺序也不受限制。此外，题目给出的数据保证至少存在一种解决方案。
首先象到hash数组法，但是不确定hash数组的固定长度，采用字典的方式：Map，其实ArrayList应该也可以。

代码

public class 用户分组 {
    public List<List<Integer>> groupThePeople(int[] groupSizes) {
    	
    	Map dictionary = new HashMap<>();
    	
    	List result = new ArrayList<List<Integer>>();
    	
    	for (int i = 0; i < groupSizes.length; i++) {
    		
    		List<Integer> tempArray;
    		//如果对应分组数量的集合不存在，创造并放入当前数据（下标）
			if (dictionary.get(groupSizes[i])==null) {
		    	tempArray = new ArrayList<>();
		    	tempArray.add(i);
				dictionary.put(groupSizes[i] , tempArray);
			}else {
				tempArray = (ArrayList<Integer>) dictionary.get(groupSizes[i]);
				tempArray.add(i);
			}
			
			//判断如果字典所存储的集合（list）满了分组数量，加入结果集并删去
			if (tempArray.size() == groupSizes[i]) {
				result.add(tempArray);
				dictionary.remove(groupSizes[i]);
			}
		}
    	
		return result;

    }
}

 

本文地址：https://blog.csdn.net/qq_37334150/article/details/110206912