【LeetCode】用户分组 Java 题解
题目描述
有 n 个人被分成数量未知的组。每个人都被标记为一个从 0 到 n - 1 的唯一 ID 。
给定一个整数数组 groupSizes ,其中 groupSizes[i] 是第 i 个人所在的组的大小。例如,如果 groupSizes[1] = 3 ,则第 1 个人必须位于大小为 3 的组中。
返回一个组列表,使每个人 i 都在一个大小为 groupSizes[i] 的组中。
每个人应该 恰好只 出现在 一个组 中,并且每个人必须在一个组中。如果有多个答案,返回其中 任何 一个。可以 保证 给定输入 至少有一个 有效的解。
思路分析
今天的算法题目是用户分组的问题,以数组的形式展现。题目描述比较长, 简单理解为对于索引 i, groupSizes[i] 是第 i 个人所在的组的大小, 结合题目
“有 n 个人被分成数量未知的组。每个人都被标记为一个从 0 到 n - 1 的唯一 ID ”, 也就是索引 i 位置的值,同时是 i。
根据上述对题目的理解,对于例子 1,n 个人表示的数组就是 [0,1,2,3,4,5,6], 然后结合每个 i 所在组的大小,groupSizes = [3,3,3,3,3,1,3]。具体来说,索引 5 位置的 groupSizes[5] = 1,索引 5 对应的数值 5, 就是其中一个分组。其他同理。理解题意之后,我们可以使用 hashMap 数据结构,讲分组在一起的元素存储成临时变量,然后在依次按照答案输出。
具体实现代码如下,供参考。
通过代码
总结
上述算法的时间复杂度是 O(n * n), 空间复杂度是 O(n)
今天这道算法题目,理解题意之后,重点考察的是对所用编程语言 API 的熟悉程度,不熟悉相关 HashMap API 的同学,建议多练习几次,我们一起掌握好这个题目!
坚持算法每日一题,加油!
版权声明: 本文为 InfoQ 作者【Albert】的原创文章。
原文链接:【http://xie.infoq.cn/article/a5176a2f24fde7165894385af】。文章转载请联系作者。
评论