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

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

🔗
jackjiang2 2013-7-22 08:54:56 | 只看该作者
全局:
本帖最后由 jackjiang2 于 2013-7-22 09:03 编辑
麻倉枼 发表于 2013-7-22 08:47
你这做法是不是需要两个array list了?虽然有一个original的 arraylist应该是必须的,但是。。所以你的做 ...

额 hashcode 会一样么 又不是 string
object 的 hashcode 貌似使用内存地址啥的 计算的吧
int 的貌似会一样吧

貌似用 hashset的话会删除 重复元素
回复

使用道具 举报

🔗
 楼主| 麻倉枼 2013-7-22 09:19:22 | 只看该作者
全局:
jackjiang2 发表于 2013-7-21 19:54
额 hashcode 会一样么 又不是 string
object 的 hashcode 貌似使用内存地址啥的 计算的吧
int 的貌似会 ...

我丫的没用过,我觉得以我的智商用hashtable可能是最明智的办法了吧,但是Big O complexity的话应该非常的慢!!

在interview的时候说这个自己应该也知道自己在讲什么。。
回复

使用道具 举报

🔗
 楼主| 麻倉枼 2013-7-22 09:26:17 | 只看该作者
全局:
上网找到这货:
muthukrishnan data stream algorithms

我就不可能看得懂这个了,至少一个晚上是不可能的,但是我只是发出来让大家分享下
回复

使用道具 举报

🔗
北美农民 2013-7-22 09:42:17 | 只看该作者
全局:
麻倉枼 发表于 2013-7-21 19:47
你这做法是不是需要两个array list了?虽然有一个original的 arraylist应该是必须的,但是。。所以你的做 ...

看你这描述不就是original 元素是1-100,没相同的么, 1到100本身就做hash值就行

而且是读一个输入hash一个, 不需要original array.   

这题没必要用bit操作, 不过你了解下还是可以的。
回复

使用道具 举报

🔗
jackjiang2 2013-7-22 09:44:28 | 只看该作者
全局:
麻倉枼 发表于 2013-7-22 09:19
我丫的没用过,我觉得以我的智商用hashtable可能是最明智的办法了吧,但是Big O complexity的话应该非常的 ...

额 哈希表是是号称查询 O(1)么 一遍扫下来 也才O(n)才对
回复

使用道具 举报

🔗
jackjiang2 2013-7-22 09:47:37 | 只看该作者
全局:
最简单的 就是 弄一个100大小的boolean数组 扫一遍原数组 有就True 没有 就 False  
扫完 再扫一遍这个boolean数组 然后 计算有几个 False的呗  这样不管有没有重复 都ok
回复

使用道具 举报

🔗
 楼主| 麻倉枼 2013-7-22 09:47:54 | 只看该作者
全局:
北美农民 发表于 2013-7-21 20:42
看你这描述不就是original 元素是1-100,没相同的么, 1到100本身就做hash值就行

而且是读一个输入has ...

你意思说用hash table么?我搞混了现在。。

回复

使用道具 举报

🔗
 楼主| 麻倉枼 2013-7-22 09:48:54 | 只看该作者
全局:
jackjiang2 发表于 2013-7-21 20:44
额 哈希表是是号称查询 O(1)么 一遍扫下来 也才O(n)才对

我基本功不好。。那到底是快还是慢?这个做法是正确的吗?
回复

使用道具 举报

🔗
北美农民 2013-7-22 09:49:49 | 只看该作者
全局:
麻倉枼 发表于 2013-7-21 19:44
请问你这个idea怎样用Java实现呢?
还有我其实bit方面很差,你能解释一下么?为什么用四个int组成一个bi ...

100个元素, 用 4个int 来表示是否出现。 为什么是4个int, 因为每个int 32 个bit, 4个int 128个bit刚好可以表示。  设这4个int分别是map1, map2, map3, map4

如果读到某个元素是66 , 那么66-32-32 = 2, 表示用map3的第2个bit表示有无。 初始一个第2个bit为1, 其余为0的变量做 "|" 操作

c = 01000000 00000000 00000000 00000000

map3 = map3 | c, 于是map3的第2个bit变1, 其余保持不变。

评分

参与人数 1大米 +5 收起 理由
xiaoyangmie + 5 赞版主

查看全部评分

回复

使用道具 举报

🔗
北美农民 2013-7-22 09:52:24 | 只看该作者
全局:
麻倉枼 发表于 2013-7-21 20:47
你意思说用hash table么?我搞混了现在。。

你别管是hash还是mash。

这个table就是判断哪个元素在, 哪个不在。

比如你读到一个元素i, 那么table[i] = true表示在就行。 读完后扫描一遍table[i], 哪个是false就没出现啊。

最笨的方法了
回复

使用道具 举报

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

本版积分规则

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