所以是啥
本质需要实现一个方法，就是从n个数里面random选一个数，但是选的时候要排除指定的k个数
我再提示一下，看下这个方法
比如现在有3个组 人数分别是
4 2 2
那其实这就不是完全随机的 只能后两个组的人和第一个组互相送。
这种情况算法怎么避免呢
我觉得如果需要保证最大匹配的话，那么匹配的策略肯定就不是随机的。
不知道是不是最优解：维护一个当前可供匹配的人数curNum，在0-curNum随机取一个数，然后把这个人和Person[curNum-1]互换。curNum -=1。然后找第二个人随机0-curNum，如果这个人不是和之前那个人在同一组的，就选他，如果是就往下找。找到后再和curNum-1互换，curNum–。
当然这也有个问题，就是有可能在找第二个人的时候，一直走到curNum，发现全都是和第一个人是一个组的，那么这样就得再从新找随机数。
那么是不是可以先统计出每个group的人数。在找第二个人数的时候，只有当产生的随机数小于curNum-group人数的是时候再往下找。
1 Like
每个group 的size是一样的吗？
应该是不一样的
楼主这是什么职位的面经啊，我马上也要面yelp，这个题好像去年11月面经里见过一次
yelp，你是要onsite还是电面了
只是电面哦楼主
你给的这个提示的链接的这个方法，每次生成元素的复杂度为O(k)，这个是最优解了吗？