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

寻找出现2次的数

🔗
AIPointH 2016-3-5 23:08:01 | 只看该作者
全局:
lzb940214 发表于 2016-3-5 19:40
xor只能用在仅有一个数字duplicated的情况,或者我认为的xor方法不是你的方法?欢迎详聊~~

先算出所有数的xor和 这个和相当于两堆数的xor和 然后找出这个xor和里的一个非零位 把数分为两堆
回复

使用道具 举报

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

嗯嗯,这个我和当时bit操作的想法是一致的。只是这个不是constant的space了,面试官就接着要求要constant space。我想了一会儿没想法,就问是我之前3中思路中的哪一种的延伸吗?他说是bit 这个想法
回复

使用道具 举报

🔗
 楼主| LBS 2016-3-6 03:55:44 | 只看该作者
全局:
AIPointH 发表于 2016-3-5 23:08
先算出所有数的xor和 这个和相当于两堆数的xor和 然后找出这个xor和里的一个非零位 把数分为两堆

能再详细点解释一下嘛? 不是很理解这个算法的意思。
回复

使用道具 举报

🔗
stellari 2016-3-7 13:57:02 | 只看该作者
全局:
AIPointH 发表于 2016-3-5 23:08
先算出所有数的xor和 这个和相当于两堆数的xor和 然后找出这个xor和里的一个非零位 把数分为两堆

这个算法不就是处理“仅有2个数字出现2次”的算法么?但是本题是那道题的扩展,即出现重复的数字个数“未知”。分成两堆之后,又怎么办呢?
回复

使用道具 举报

🔗
stellari 2016-3-9 12:21:30 | 只看该作者
全局:
lzb940214 发表于 2016-3-5 10:12
我觉得楼上强行占用原数组空间的方法不太好,因为这假设了原数组必须是用int储存的,如果用uint怎么办?
...

实际面试时,这个问题我会先跟面试官确认清楚。但是我觉得如果是uint,O(1)内存的限制就很难做到(至少我现在也没想出来该如何做到,而且目前好像也没有人给出合理的解法)。因此,如果楼主没理解错题的话,我觉得最合理的问答上下文就是:“在int数组中------>用符号位bit来实现之。”
回复

使用道具 举报

🔗
Zestinc 2016-3-11 06:58:14 | 只看该作者
全局:
LBS 发表于 2016-3-6 03:55
能再详细点解释一下嘛? 不是很理解这个算法的意思。

我觉得他说的是https://leetcode.com/problems/single-number-iii/这道题,和你的这道题不一样。
回复

使用道具 举报

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

本版积分规则

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