面试题 finding missing value - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

面试题 finding missing value

面试题 finding missing value# JobHunting - 待字闺中

l*d2013-03-04 08:03

1 楼

Unsorted数组含数字范围1-n,其中里面有一个数missing，n非常大，内存不能放下这个
数组
常规的解法数学求和来做可能溢出
还有其他方法么？
今天被问到了提示了一个用概率来解没太想明白怎么用貌似什么90 percent 不太清
楚，谁能解释一下么，谢谢

f*e2013-03-04 08:03

2 楼

quicksort similar?

【在 l***d 的大作中提到】

: Unsorted数组含数字范围1-n,其中里面有一个数missing，n非常大，内存不能放下这个
: 数组
: 常规的解法数学求和来做可能溢出
: 还有其他方法么？
: 今天被问到了提示了一个用概率来解没太想明白怎么用貌似什么90 percent 不太清
: 楚，谁能解释一下么，谢谢

s*r2013-03-04 08:03

3 楼

会不会是用经典书里random那章的内容来做？我最讨厌那章了。。

b*u2013-03-04 08:03

4 楼

+1

【在 f*****e 的大作中提到】

: quicksort similar?

r*e2013-03-04 08:03

5 楼

用XOR求和没有溢出问题

【在 l***d 的大作中提到】

o*d2013-03-04 08:03

6 楼

cc150有一题是说
把1-n分成大小一样的块统计每个块里面的数存在于数组中的个数
（假设没有duplicate）
比如每个块是1000个数但发现之统计出999个数
那么missing的数就在那个块里面
然后再找一遍那个数组就知道了

【在 l***d 的大作中提到】

G*A2013-03-04 08:03

7 楼

如果"内存不能放下这个数组", quicksort也没法用巴？

【在 f*****e 的大作中提到】

: quicksort similar?

l*d2013-03-04 08:03

8 楼

CLRS里面？

【在 s**********r 的大作中提到】

: 会不会是用经典书里random那章的内容来做？我最讨厌那章了。。

f*t2013-03-04 08:03

9 楼

异或所有的数，再跟1到n异或一遍
O(n)时间O(1)空间

l*a2013-03-04 08:03

10 楼

ls 正解

【在 f*******t 的大作中提到】

: 异或所有的数，再跟1到n异或一遍
: O(n)时间O(1)空间

s*r2013-03-04 08:03

11 楼

是阿。。。
因为我不喜欢那章，所以粗略的看一下，学的也不好。。。所以也不知道是不是。。。

【在 l***d 的大作中提到】

: CLRS里面？

l*i2013-03-04 08:03

12 楼

another way is to use partition. split the numbers into two halves, one with
<= n/2, and the other with >n/2, then recurse on one with a smaller count.

2024-01-28 18:01

2024-01-09 19:01

2024-01-07 18:01

2024-01-06 18:01

2024-01-06 18:01

2023-12-13 17:12

2023-12-02 07:12

2023-11-26 18:11

中美航班重磅消息！每周85班，直飞更方便！

微软、亚马逊、谷歌大裁员！哪些科技和零售公司有缩减规模计划？

中国外长王毅：中美关系已经止跌回稳

脱轨事故造成20多人受伤联邦调查纽约市全部地铁系统

更多 2024-06-02 的新闻