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

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

🔗
 楼主| 麻倉枼 2013-7-23 07:01:46 | 只看该作者
全局:
jackjiang2 发表于 2013-7-22 01:54
亲 本质思想上 最笨的方法 和 位运算的方法 是一致的 但是位运算的空间复杂度低 时间上面也更快 用128bit ...

我都说过是北美兄之前那贴说那是最笨的方法所以我才follow他的说法去说。。怎么还是一直针对这句话?
我不觉得那是最笨的方法,甚至我觉得这是很实际的做法。。我对bitset真的不是很会,所以我看不出它们的共同之处。。
回复

使用道具 举报

🔗
jackjiang2 2013-7-23 08:57:56 | 只看该作者
全局:
本帖最后由 jackjiang2 于 2013-7-23 08:59 编辑
麻倉枼 发表于 2013-7-23 07:01
我都说过是北美兄之前那贴说那是最笨的方法所以我才follow他的说法去说。。怎么还是一直针对这句话?
我 ...

额 我回帖的时候 没看上面的那个版主的帖子 额 so sorry
i don't mean that
回复

使用道具 举报

🔗
 楼主| 麻倉枼 2013-7-23 11:10:35 | 只看该作者
全局:
jackjiang2 发表于 2013-7-22 19:57
额 我回帖的时候 没看上面的那个版主的帖子 额 so sorry
i don't mean that

其实没关系,没想到这也被你们发觉到我当下寒意怏然呀。。
回复

使用道具 举报

🔗
坑王 2013-7-23 23:59:06 | 只看该作者
全局:
GTea 发表于 2013-7-23 04:31
能详细讲一下么?

running time是多少?

我看错题目了。。这个方法只能找缺一个数的。。。囧。
XOR的性质就是偶数个相同的数XOR就是抵消掉了。
不用真的构造一个一个数组啊,来个循环就好了。空间应该就是O(N),总是要吧原来的data读进来吧。。时间也是O(N)。
回复

使用道具 举报

🔗
GTea 2013-7-24 04:33:40 | 只看该作者
全局:
坑王 发表于 2013-7-23 23:59
我看错题目了。。这个方法只能找缺一个数的。。。囧。
XOR的性质就是偶数个相同的数XOR就是抵消掉了。
...

哦,明白了,过一遍就行了,O(n).
回复

使用道具 举报

🔗
lzhjoeytri 2013-7-28 11:21:34 | 只看该作者
全局:
一群技术帝
回复

使用道具 举报

🔗
LinRaise 2013-8-1 18:25:25 | 只看该作者
全局:
直接调用快排的partition的改良版,空间复杂度可以降到o(1),时间复杂度可以降到o(lgn),只是有缺点,就是需要交换数组位置.还有一种不需要的,相对麻烦一些.
回复

使用道具 举报

🔗
北美农民 2013-8-12 00:58:45 | 只看该作者
全局:
LinRaise 发表于 2013-8-1 05:25
直接调用快排的partition的改良版,空间复杂度可以降到o(1),时间复杂度可以降到o(lgn),只是有缺点,就是需 ...

麻烦详细说一下 时间复杂度为lgn的快排??
回复

使用道具 举报

🔗
zercal 2013-8-15 10:44:53 | 只看该作者
全局:
北美农民 发表于 2013-8-12 00:58
麻烦详细说一下 时间复杂度为lgn的快排??

就是在做partition的时候,因为只少一个数,所以每次partition完只用往一边递归, (根据partition中位数大小和两边部分大小可以判断往那边),然后总体下来就是log n.
不过缺的数多的话就不好了.
回复

使用道具 举报

🔗
北美农民 2013-8-15 12:54:19 | 只看该作者
全局:
zercal 发表于 2013-8-14 21:44
就是在做partition的时候,因为只少一个数,所以每次partition完只用往一边递归, (根据partition中位数大小 ...

LZ的问题是K个数吧? 而且就算只少一个数, 只recurse一边, 那也是O(n) = O(patition(n)) + O(left) 或者 O(right), 这个递推公式最后的结果复杂度也不是log n啊?  我理解错了?
回复

使用道具 举报

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

本版积分规则

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