📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
楼主: LBS
跳转到指定楼层
上一主题 下一主题
收起左侧

寻找出现2次的数

🔗
Zestinc 2016-3-2 18:23:44 | 只看该作者
全局:
stellari 发表于 2016-3-2 15:02
这题最容易想到的思路就是使用一个HashSet记录已经出现过1次的数字。不过既然数字的范围在1~n内且连续,所 ...

符号位还能这么用,长经验了
回复

使用道具 举报

🔗
staycrazy 2016-3-3 03:38:46 | 只看该作者
全局:
fish444555 发表于 2016-3-2 05:29
确实引用可以避免重新开辟空间,谢谢提醒。至于不能改变原来的数组而实现 O(1) space & O(n) complexity ...

其实使用符号位挺作弊的,相当于使用了1/word的额外空间——万一人家数组是无符号的byte怎么办?

如果并不要求精确匹配,这道题目是bloom filter的原型。
回复

使用道具 举报

🔗
 楼主| LBS 2016-3-4 02:26:58 | 只看该作者
全局:
stellari 发表于 2016-3-2 15:02
这题最容易想到的思路就是使用一个HashSet记录已经出现过1次的数字。不过既然数字的范围在1~n内且连续,所 ...

多谢分享!这个负数反过来确实很妙!
回复

使用道具 举报

🔗
 楼主| LBS 2016-3-4 02:30:21 | 只看该作者
全局:
staycrazy 发表于 2016-3-3 03:38
其实使用符号位挺作弊的,相当于使用了1/word的额外空间——万一人家数组是无符号的byte怎么办?

如果 ...

面试官最后要希望我延用我之前bit的思想解这题,我只想出了一个最简单的想法,就是用n/32 个 32bit的数表示(这样并不是constant space),如此操作,每一位就是代表一个容器。 我再回顾一下bloom filter ,多谢。
回复

使用道具 举报

🔗
 楼主| LBS 2016-3-5 08:48:10 | 只看该作者
全局:
staycrazy 发表于 2016-3-3 03:38
其实使用符号位挺作弊的,相当于使用了1/word的额外空间——万一人家数组是无符号的byte怎么办?

如果 ...

你好,能请教一下此题如何套用bloom filter吗?
回复

使用道具 举报

🔗
lzb940214 2016-3-5 10:12:15 | 只看该作者
全局:
我觉得楼上强行占用原数组空间的方法不太好,因为这假设了原数组必须是用int储存的,如果用uint怎么办?
另外关于bloom filter的方法,我觉得额外开常数空间是不太可行的。(应该说显然是不可行的,因为常数空间能标示的状态数也就是常数)
不过一般这种题目说是哦o(1),大多是o(logn),否则连counter都开不起。
回复

使用道具 举报

🔗
lefttree 2016-3-5 16:56:54 | 只看该作者
全局:
LBS 发表于 2016-3-4 02:30
面试官最后要希望我延用我之前bit的思想解这题,我只想出了一个最简单的想法,就是用n/32 个 32bit的数表 ...

那面试官的意思应该是用bitmap,因为之前已经告诉了范围是1-n, 每一位bit代表一个数字,每出现一次就xor, 最后是0的应该就是出现两次的数。
回复

使用道具 举报

🔗
lzb940214 2016-3-5 18:12:43 | 只看该作者
全局:
lefttree 发表于 2016-3-5 16:56
那面试官的意思应该是用bitmap,因为之前已经告诉了范围是1-n, 每一位bit代表一个数字,每出现一次就xor,  ...

感觉用bitmap就太trivial了,没有冒犯你的意思= =
回复

使用道具 举报

🔗
AIPointH 2016-3-5 18:35:30 | 只看该作者
全局:
这个就是用xor 认识一个学长面试刚遇到过 - -
回复

使用道具 举报

🔗
lzb940214 2016-3-5 19:40:35 | 只看该作者
全局:
AIPointH 发表于 2016-3-5 18:35
这个就是用xor 认识一个学长面试刚遇到过 - -

xor只能用在仅有一个数字duplicated的情况,或者我认为的xor方法不是你的方法?欢迎详聊~~
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表