l***d
发帖数: 12 | 1 Unsorted数组含数字范围1-n,其中里面有一个数missing，n非常大，内存不能放下这个
数组
常规的解法 数学求和来做 可能溢出
还有其他方法么？
今天被问到了 提示了一个用概率来解 没太想明白怎么用 貌似什么90 percent 不太清
楚，谁能解释一下么，谢谢 |
f*****e
发帖数: 2992 | 2 quicksort similar?
【在 l***d 的大作中提到】
: Unsorted数组含数字范围1-n,其中里面有一个数missing，n非常大，内存不能放下这个
: 数组
: 常规的解法 数学求和来做 可能溢出
: 还有其他方法么？
: 今天被问到了 提示了一个用概率来解 没太想明白怎么用 貌似什么90 percent 不太清
: 楚，谁能解释一下么，谢谢
|
s**********r
发帖数: 8153 | 3 会不会是用经典书里random那章的内容来做？我最讨厌那章了。。 |
b*****u
发帖数: 648 | 4 +1
【在 f*****e 的大作中提到】
: quicksort similar?
|
r*******e
发帖数: 7583 | 5 用XOR求和没有溢出问题
【在 l***d 的大作中提到】
: Unsorted数组含数字范围1-n,其中里面有一个数missing，n非常大，内存不能放下这个
: 数组
: 常规的解法 数学求和来做 可能溢出
: 还有其他方法么？
: 今天被问到了 提示了一个用概率来解 没太想明白怎么用 貌似什么90 percent 不太清
: 楚，谁能解释一下么，谢谢
|
o****d
发帖数: 2835 | 6 cc150有一题是说
把1-n分成大小一样的块 统计每个块里面的数存在于数组中的个数
（假设没有duplicate）
比如每个块是1000个数 但发现之统计出999个数
那么missing的数就在那个块里面
然后再找一遍那个数组就知道了
【在 l***d 的大作中提到】
: Unsorted数组含数字范围1-n,其中里面有一个数missing，n非常大，内存不能放下这个
: 数组
: 常规的解法 数学求和来做 可能溢出
: 还有其他方法么？
: 今天被问到了 提示了一个用概率来解 没太想明白怎么用 貌似什么90 percent 不太清
: 楚，谁能解释一下么，谢谢
|
G****A
发帖数: 4160 | 7 如果"内存不能放下这个数组", quicksort也没法用巴？
【在 f*****e 的大作中提到】
: quicksort similar?
|
l***d
发帖数: 12 | 8 CLRS里面？
【在 s**********r 的大作中提到】
: 会不会是用经典书里random那章的内容来做？我最讨厌那章了。。
|
f*******t
发帖数: 7549 | 9 异或所有的数，再跟1到n异或一遍
O(n)时间O(1)空间 |
l*****a
发帖数: 177 | 10 ls 正解
【在 f*******t 的大作中提到】
: 异或所有的数，再跟1到n异或一遍
: O(n)时间O(1)空间
|
s**********r
发帖数: 8153 | 11 是阿。。。
因为我不喜欢那章，所以粗略的看一下，学的也不好。。。所以也不知道是不是。。。
【在 l***d 的大作中提到】
: CLRS里面？
|
l***i
发帖数: 1309 | 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. |
