黑车店面，碰到没见过的题

fin

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

去年年末找工作的面经了。在本版记录一下一些自认为非常规的题，以免以后忘记给定一个数组，要求找到尽可能多的pair，使得每个pair的第二个数是第一个数的两倍<

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

1, 2, 2, 4]，输出就是[(1, 2), (2, 4)]。但是如果输入是[1, 2, 4]，输出就只能是[(1, 2)]或者[(2, 4)]其中之一。不能编辑帖子真烦

say543

lz 什么组的?

hpplayer

楼主咋做的？
我想到可以先排序，然后用个HASHSET记录访问过的值，对新的值，看看SET里有没有/2，有的话，就移除同时输出个pair?

fin

我也是差不多这样做。只是输入可能有duplicates，所以要用multibag而不是hashset。但是排序要O(n*logn)，感觉应该有O(n)的方案。当然还是给我pass了

鬼雨澜蓝

刷题网救污丝

loveJoyce123

map, key是出现的数，value是出现了几次，用一次就value-1，value==0 就把这个key去掉（也可以不去掉，下次要用的时候check 一下value是不是0），应该是O(n)吧？

Venus

我的想法是不sorted的话就是one pass但是费空间
每次查看 cur * 2 or cur / 2存不存在
然后结果就是用set来去重吧

fin

不sort的话，有可能会miss掉一些pairs。例如[2, 4, 1, 8]，如果你把2和4配对，剩下1和8就没法配了。正确答案是1和2配，4和8配