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

我又来秀智商下限了,How to find Kth missing numbers in an array?

🔗
jackjiang2 2013-7-22 09:53:06 | 只看该作者
全局:
麻倉枼 发表于 2013-7-22 09:48
我基本功不好。。那到底是快还是慢?这个做法是正确的吗?

快得一b呀 哈希表不是灰常快么
回复

使用道具 举报

🔗
jackjiang2 2013-7-22 09:53:35 | 只看该作者
全局:
北美农民 发表于 2013-7-22 09:49
100个元素, 用 4个int 来表示是否出现。 为什么是4个int, 因为每个int 32 个bit, 4个int 128个bit刚好 ...

膜拜 下 版主君

点评

你好  发表于 2013-7-22 09:55
回复

使用道具 举报

🔗
 楼主| 麻倉枼 2013-7-22 10:16:15 | 只看该作者
全局:
北美农民 发表于 2013-7-21 20:49
100个元素, 用 4个int 来表示是否出现。 为什么是4个int, 因为每个int 32 个bit, 4个int 128个bit刚好 ...

太神奇了。。不懂呀。。我想那个最笨的方法就是solution了。。这个怎么会想到?数学要有多强呀。。

点评

我说那个最笨的方法其实是农民兄之前那贴提到的,后面说怎么会想到是说之前那个bit方法的牛人数学很强  发表于 2013-7-22 11:09
哇塞这样也行。。我自己现在才意识到。。  发表于 2013-7-22 11:06
低端黑= =  发表于 2013-7-22 10:18

评分

参与人数 1大米 +5 收起 理由
jackjiang2 + 5 额 确实有点黑

查看全部评分

回复

使用道具 举报

🔗
 楼主| 麻倉枼 2013-7-22 10:18:45 | 只看该作者
全局:
jackjiang2 发表于 2013-7-21 20:47
最简单的 就是 弄一个100大小的boolean数组 扫一遍原数组 有就True 没有 就 False  
扫完 再扫一遍这个boo ...

没错,我觉得这个办法挺好的。。
回复

使用道具 举报

🔗
jackjiang2 2013-7-22 14:54:31 | 只看该作者
全局:
本帖最后由 jackjiang2 于 2013-7-22 14:55 编辑
麻倉枼 发表于 2013-7-22 10:16
太神奇了。。不懂呀。。我想那个最笨的方法就是solution了。。这个怎么会想到?数学要有多强呀。。

亲 本质思想上 最笨的方法 和 位运算的方法 是一致的 但是位运算的空间复杂度低 时间上面也更快 用128bit代替了 那个boolean数组 然后用 | 运算代替了check原数据里面缺不缺这个数
好像是称作 位图 吧
回复

使用道具 举报

🔗
坑王 2013-7-22 16:37:46 | 只看该作者
全局:
另外搞一个全的1到100的数组,和之前的那个残缺的数据逐个xor,最后的结果就是少掉的那个
回复

使用道具 举报

🔗
GTea 2013-7-23 03:40:53 | 只看该作者
全局:
北美农民 发表于 2013-7-22 09:49
100个元素, 用 4个int 来表示是否出现。 为什么是4个int, 因为每个int 32 个bit, 4个int 128个bit刚好 ...

讲得真清楚 good
回复

使用道具 举报

🔗
GTea 2013-7-23 03:54:52 | 只看该作者
全局:
个人觉得两个办法:

1 建hashtable,然后过一遍。running complexity O(n), space complexity O(n). 优点是省时间,缺点是hashtable费空间,如果是大量的数,hashtable就会很大。

2 就地排序,然后过一遍。running complexity O(nlogn), space complexity O(1)。优点是不需要额外的空间,省空间,缺点是running time多些。

am I correct?
回复

使用道具 举报

🔗
GTea 2013-7-23 04:31:24 | 只看该作者
全局:
坑王 发表于 2013-7-22 16:37
另外搞一个全的1到100的数组,和之前的那个残缺的数据逐个xor,最后的结果就是少掉的那个

能详细讲一下么?

running time是多少?

搞一个全的1到100的数组:O(n)

和之前的那个残缺的数据逐个xor:O(n^2)

这貌似很慢啊。。。有什么特别的优势么?

回复

使用道具 举报

🔗
 楼主| 麻倉枼 2013-7-23 06:59:37 | 只看该作者
全局:
坑王 发表于 2013-7-22 03:37
另外搞一个全的1到100的数组,和之前的那个残缺的数据逐个xor,最后的结果就是少掉的那个

怎么大家好像对bitset的理解和运用都那么强?
一说到这种问题时我第一时间也是想弄hashtable之类的,从来没想过要用bit还有arithmetic operation。。。
回复

使用道具 举报

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

本版积分规则

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