算法动画：Leetcode Q1282 人员分组| 第01期(试水)
By 青衣极客 Blue Geek In 2020-05-27
我们在Leetcode交流社区中，是以源码的形式来分享解题思路的，但这并不是一种简单易推广的方式。特别是对于刚入门算法的朋友而言，从源码中理解算法思路并不是一件容易的事情。 即使对于很有经验的朋友，阅读源码也是最后的选项。
现在毫无疑问已经进入了一个读图的时代，人们越来越没有耐心看很多的文字，获取知识的渠道也从书本转移一部分到了视频。富媒体比纯文本更加丰富的表达方式更有利于吸引眼球、降低沟通成本、以及扩展表达的维度。 对于算法这种本身就非常抽象的知识就更需要借助视频的传播力来降低沟通的门槛。
所以，就准备开始制作算法动画的视频，来讨论一些常用的算法以及Leetcode题解，后续会以专题系列的形式发布算法讲解动画。主要发布平台为Youtube、微信公众号、Bilibili以及西瓜视频。 下面就是本次试水的第一个视频，欢迎感兴趣的朋友参与到社区的讨论中。
如果有推荐解说的题目或者建议，可以在评论区留言或者私信。想要查看源代码，可以点击源代码链接
解说词
大家好，欢迎来到青衣极客频道。
目前在我们的Leetcode交流社区中是以源码的形式分享算法思想的，这对新手而言非常的不友好。 事实上，即使对于老司机，要从源码中很快了解算法思想也并不容易。 所以，频道打算开一个视频动画解说Leetcode算法的专栏。 首先，就通过Leetcode Q1282题来试个水，因为之前听人说很难看懂Q282的题意。 之后会分算法专题，按照系列来推出视频讲解动画。
1. 题意重述
Q1282题的意思是说，需要将一群n人分配到若干个群中，每个人都有一个唯一ID，从 0 开始，一直到 n-1。 在程序中，我们能够区别人员的方法也就是使用ID。 现在，每个人都有一个要求，那就是只加入指定大小的群。 这个场景比较像是团体旅游时，分配酒店住宿是单人间还是双人间。 比如，在当前的例子中，大多数的人都要求加入一个3人群，有一个人要求加入1人群。 既然如此，那就可以将五号单独成群，然后其他的人员分配到两个三人群中。 当然，这样的分配方案并不唯一，相同人数的群之间交换成员就能构成不一样的解。
OK，题意明确之后，我们该如何设计一个算法完成这种人员分配呢？
方案1
我们逐个取出待分配的人员，如果当前人员要求的群不存在或者存在但没有空位，则新建一个符合要求的群； 如果当前人员要求的群已经存在，并且有空位，则安排进去。
比如，这里的3号人员就是因为满足要求的群没有空位，所以新建一个；5号人员因为没有满足要求的群，所以新建。 其他的都是找到符合要求并且有空位的群安排进去即可。
这样设计的算法时间复杂度是多少呢？ 在最坏的情况下是 O(n^2)
方案2
我们或许可以优化一下这个算法，请看方案2. 同样是逐个检查每个人及其要求的群大小，但是首先不直接分配，而是将有相同需要的人员记录在一起。 记录完成后，直接将提出相同要求的人员等分成若干组即可。 这样的方法运行耗时关键在于建立群大小到人员的映射，时间复杂度是O(nlog(n)) 而后续的分配则非常快速，复杂度可以忽略不计。 因此整体的时间复杂度是 O(nlog(n)). 最后，本频道视频的发布渠道暂定为这四个，对相关内容感兴趣的朋友，欢迎选择方便的平台观看。
COMMENT
博客评论区功能由Github Issue提供，提交Issue时请以本文标题为话题。
"BG107-算法动画：Leetcode Q1282 人员分组| 第01期(试水)"