药铺电面

在面经里面看到过，但是扫了一眼没想，果然遇到了。贡献一个数据点，攒点人品

您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

请问随机配对的话，能不能把list拆成两份然后直接用 random.shuffle(list)，然后再用指针遍历? O(n)复杂度。
这样会不会太简单了哈哈

flyMontain 发表于 2019-5-18 16:34
暴力解可以两个loop，看到不同组的就match，同时要维护一个已经访问的set。

楼主我问一下哈，如果组不一样的话loop应该有漏洞吧，如果是随机的a组有5个b组有3个c组有两个 那我们该做的应该是确保不要把b跟c组成一队因为这样就可能会出现a组没有可以分配的人了吧。我的思路是维护一个pq 然后每次找组里人数最大的跟里面的人配对 然后再把pq放进去 但看完你的思路感觉我又很疑惑。。。

olyescape 发表于 2019-5-19 13:11
谢谢～你好，可以不可以说下第一问的思路呢？怎么想都是O(n^2)..

第一问没有很复杂，如果是每次的list都是已经shuffle过的，直接相邻的两两配对即可

请问follow up怎么做的呢

olyescape 发表于 2019-5-18 06:02
请问follow up怎么做的呢

暴力解可以两个loop，看到不同组的就match，同时要维护一个已经访问的set。

谢谢～你好，可以不可以说下第一问的思路呢？怎么想都是O(n^2)..

flyMontain 发表于 2019-5-22 02:25
第一问没有很复杂，如果是每次的list都是已经shuffle过的，直接相邻的两两配对即可

谢谢！

请问暴力解可以过吗