a*********0
发帖数: 2727 | 1 Find or determine non existence of a number in a sorted list of N numbers
where the numbers range over M, M >> N. require O(lgn) |
r******l
发帖数: 10760 | |
a*********0
发帖数: 2727 | 3 道理简单，可是实现代码发现很头大
【在 r******l 的大作中提到】
: 不就是binary search么？
|
r******l
发帖数: 10760 | 4 binary search有啥头大的地方？
【在 a*********0 的大作中提到】
: 道理简单，可是实现代码发现很头大
|
g*****k
发帖数: 623 | 5 do the binary search by pivot M/2, always choose the smaller half with
missing number.
【在 a*********0 的大作中提到】
: Find or determine non existence of a number in a sorted list of N numbers
: where the numbers range over M, M >> N. require O(lgn)
|
a*********0
发帖数: 2727 | 6 then how do you decide which one is missing. when should you stop?
【在 g*****k 的大作中提到】
: do the binary search by pivot M/2, always choose the smaller half with
: missing number.
|
g*****k
发帖数: 623 | 7 Let's say you have two indices, low and high, to index the array,
but you also have two numbers, start and end to denote the number range.
The search will stop when low>high, and the missing number is any number in
[start, end]
The initial values:
low = 0;
high = N-1;
start = 1;
end = M;
【在 a*********0 的大作中提到】
: then how do you decide which one is missing. when should you stop?
|
a*********0
发帖数: 2727 | 8 good. this might work i think
in
【在 g*****k 的大作中提到】
: Let's say you have two indices, low and high, to index the array,
: but you also have two numbers, start and end to denote the number range.
: The search will stop when low>high, and the missing number is any number in
: [start, end]
: The initial values:
: low = 0;
: high = N-1;
: start = 1;
: end = M;
|
c*********t
发帖数: 2921 | 9 Hi, absolute100,
这些数是存在一个array[]里，还是存在一个singly linked-list?
谢谢！
【在 a*********0 的大作中提到】
: Find or determine non existence of a number in a sorted list of N numbers
: where the numbers range over M, M >> N. require O(lgn)
|
a********m
发帖数: 15480 | |
|
|
a*********0
发帖数: 2727 | 11 array i think
【在 c*********t 的大作中提到】
: Hi, absolute100,
: 这些数是存在一个array[]里，还是存在一个singly linked-list?
: 谢谢！
|
p*****u
发帖数: 310 | |
a********m
发帖数: 15480 | 13 恩。基本算法好像没啥不一样。细节需要注意点就好了。 |
k****n
发帖数: 1334 | 14 me neither
【在 p*****u 的大作中提到】
: 还是不明白跟一般的二分查找有啥不同？
|
a*********0
发帖数: 2727 | 15 write down entire code you'll know why
【在 k****n 的大作中提到】
: me neither
|
k****n
发帖数: 1334 | 16 题目没看懂，是给你一个数，让你找这个数吗？
range M是神马用？
【在 a*********0 的大作中提到】
: write down entire code you'll know why
|
a*********0
发帖数: 2727 | 17 给一个有序的M到M+N的序列，找不在这个序列中的数。要去lgn
【在 k****n 的大作中提到】
: 题目没看懂，是给你一个数，让你找这个数吗？
: range M是神马用？
|
a*********0
发帖数: 2727 | 18 我发现序列奇偶个数要分开考虑？
比如
1 2 3 5 6《-----A[mid]是3， value-mid=(1+6)/2=3, A[mid]==value-mid, 向右找
1 3 4 5 《-----A[mid]是3， value-mid=(1+5)/2=3, A[mid]==value-mid, 却向左找
这题太恶心啦
in
【在 g*****k 的大作中提到】
: Let's say you have two indices, low and high, to index the array,
: but you also have two numbers, start and end to denote the number range.
: The search will stop when low>high, and the missing number is any number in
: [start, end]
: The initial values:
: low = 0;
: high = N-1;
: start = 1;
: end = M;
|
k****n
发帖数: 1334 | 19 那getback的解法就不make sense
是说有一个N个数的连续有序序列，数值都在[1,M]内，但是中间缺了个数，找它？
【在 a*********0 的大作中提到】
: 给一个有序的M到M+N的序列，找不在这个序列中的数。要去lgn
|
k****n
发帖数: 1334 | 20 终于看明白了。。就是bst加值的判断
你再想想吧
【在 a*********0 的大作中提到】
: 我发现序列奇偶个数要分开考虑？
: 比如
: 1 2 3 5 6《-----A[mid]是3， value-mid=(1+6)/2=3, A[mid]==value-mid, 向右找
: 1 3 4 5 《-----A[mid]是3， value-mid=(1+5)/2=3, A[mid]==value-mid, 却向左找
: 这题太恶心啦
:
: in
|
|
|
a*********0
发帖数: 2727 | 21 bst加值是什么？说英文，中文看不懂
【在 k****n 的大作中提到】
: 终于看明白了。。就是bst加值的判断
: 你再想想吧
|
k****n
发帖数: 1334 | 22 你先把题目说清楚了，是缺一个数还是缺一堆数
【在 a*********0 的大作中提到】
: bst加值是什么？说英文，中文看不懂
|
a********m
发帖数: 15480 | 23 折半找是不是缺数就可以了。不管个数奇偶。
【在 a*********0 的大作中提到】
: 我发现序列奇偶个数要分开考虑？
: 比如
: 1 2 3 5 6《-----A[mid]是3， value-mid=(1+6)/2=3, A[mid]==value-mid, 向右找
: 1 3 4 5 《-----A[mid]是3， value-mid=(1+5)/2=3, A[mid]==value-mid, 却向左找
: 这题太恶心啦
:
: in
|
a********m
发帖数: 15480 | 24 恩。。。。你断句断错了。。。
【在 a*********0 的大作中提到】
: bst加值是什么？说英文，中文看不懂
|
a*********0
发帖数: 2727 | 25 一个
【在 k****n 的大作中提到】
: 你先把题目说清楚了，是缺一个数还是缺一堆数
|
a*********0
发帖数: 2727 | 26 缺一堆找一个我觉得思路是一样的吧
【在 k****n 的大作中提到】
: 你先把题目说清楚了，是缺一个数还是缺一堆数
|
a********m
发帖数: 15480 | 27 是题目是不是清楚的问题。缺一堆可能是随便找一个，题目就很不一样了。
【在 a*********0 的大作中提到】
: 缺一堆找一个我觉得思路是一样的吧
|
k****n
发帖数: 1334 | 28 bst(a, low, high):
if (low >= high) 找到了就
mid=(low+high)/2;
if(a[mid]-a[low]>mid - low)
bst(a, low, mid)
else
bst(a, mid, high)
【在 a*********0 的大作中提到】
: 一个
|
k****n
发帖数: 1334 | 29 缺一堆要赵全很难，logN不行把
【在 a*********0 的大作中提到】
: 缺一堆找一个我觉得思路是一样的吧
|
a*********0
发帖数: 2727 | 30 当然是随便找到一个
【在 k****n 的大作中提到】
: 缺一堆要赵全很难，logN不行把
|
|
|
k****n
发帖数: 1334 | 31 那算法一样
【在 a*********0 的大作中提到】
: 当然是随便找到一个
|
a********m
发帖数: 15480 | 32 二分不一定最好。
【在 k****n 的大作中提到】
: 那算法一样
|
k****n
发帖数: 1334 | 33 whatever as long as logN:)
【在 a********m 的大作中提到】
: 二分不一定最好。
|
g*****k
发帖数: 623 | 34 这道题条件是M >> N,
那我们就看A[N/2],有三种情况:
1) A[N/2]==N/2, 那么(N/2..M]中一定有数不在 A[N/2+1]..A[N]中，取右边
2）A[N/2]
3）A[N/2]>N/2, 那么[0,N/2）中一定有数不在A[0]..A[N/2-1]中 取左边
【在 a*********0 的大作中提到】
: 我发现序列奇偶个数要分开考虑？
: 比如
: 1 2 3 5 6《-----A[mid]是3， value-mid=(1+6)/2=3, A[mid]==value-mid, 向右找
: 1 3 4 5 《-----A[mid]是3， value-mid=(1+5)/2=3, A[mid]==value-mid, 却向左找
: 这题太恶心啦
:
: in
|
a********m
发帖数: 15480 | 35 恩。级别一样。
【在 k****n 的大作中提到】
: whatever as long as logN:)
|
a*********0
发帖数: 2727 | 36 好像不对呦
比如 1 3 4 5
a[mid]-a[low]=a[1]-a[0]=2>1-0,按你的算法向右找了，实际在左边
right？
【在 k****n 的大作中提到】
: bst(a, low, high):
: if (low >= high) 找到了就
: mid=(low+high)/2;
: if(a[mid]-a[low]>mid - low)
: bst(a, low, mid)
: else
: bst(a, mid, high)
|
a*********0
发帖数: 2727 | 37 M是值得范围，N是数组的个数，应该是A[N/2]==M/2?
这题恶心在我举的那个例子，由于偶数个数情况下中值是2个数左边那个，结果会有冲
突？
【在 g*****k 的大作中提到】
: 这道题条件是M >> N,
: 那我们就看A[N/2],有三种情况:
: 1) A[N/2]==N/2, 那么(N/2..M]中一定有数不在 A[N/2+1]..A[N]中，取右边
: 2）A[N/2]: 3）A[N/2]>N/2, 那么[0,N/2）中一定有数不在A[0]..A[N/2-1]中 取左边
|
a********m
发帖数: 15480 | 38 把<改称>
【在 a*********0 的大作中提到】
: 好像不对呦
: 比如 1 3 4 5
: a[mid]-a[low]=a[1]-a[0]=2>1-0,按你的算法向右找了，实际在左边
: right？
|
g*****k
发帖数: 623 | 39 如果题中条件是数组中的值的范围是[0..M],那么测试就是A[N/2]==N/2;
你自己带你那个例子看看就知道了。
M是值得范围，N是数组的个数，应该是A[N/2]==M/2?
这题恶心在我举的那个例子，由于偶数个数情况下中值是2个数左边那个，结果会有冲
突？
【在 a*********0 的大作中提到】
: M是值得范围，N是数组的个数，应该是A[N/2]==M/2?
: 这题恶心在我举的那个例子，由于偶数个数情况下中值是2个数左边那个，结果会有冲
: 突？
|
a********m
发帖数: 15480 | |
|
|
b*******8
发帖数: 37364 | 41 换个思路，也可以用随机算法。
随便取个范围内的数，二分查找是否在里面，如在则再换个数
M里最多只有N个数在数组里，平均取数的次数约等于M/(M-N)，由于M>>N，只比1大一点
点。 |
a*********0
发帖数: 2727 | 42 good，这个实际是这题的bonus
【在 b*******8 的大作中提到】
: 换个思路，也可以用随机算法。
: 随便取个范围内的数，二分查找是否在里面，如在则再换个数
: M里最多只有N个数在数组里，平均取数的次数约等于M/(M-N)，由于M>>N，只比1大一点
: 点。
|
a*********0
发帖数: 2727 | 43 最后如何获取结束值？好像情况很复杂
另外N应该是N-1吧，数组是0....N-1
【在 g*****k 的大作中提到】
: 这道题条件是M >> N,
: 那我们就看A[N/2],有三种情况:
: 1) A[N/2]==N/2, 那么(N/2..M]中一定有数不在 A[N/2+1]..A[N]中，取右边
: 2）A[N/2]: 3）A[N/2]>N/2, 那么[0,N/2）中一定有数不在A[0]..A[N/2-1]中 取左边
|
a*********0
发帖数: 2727 | 44 结束条件不对
1 2 3 5 6
final low=5 high=6 =》mid=(low+high)/2=5, a[5]-a[5]==5-5, go right(low=6
high=6, it should be mid+1 right?), actually missing is 4
【在 k****n 的大作中提到】
: bst(a, low, high):
: if (low >= high) 找到了就
: mid=(low+high)/2;
: if(a[mid]-a[low]>mid - low)
: bst(a, low, mid)
: else
: bst(a, mid, high)
|
i**********e
发帖数: 1145 | 45 这个 binary search 就可以搞定。
主要就是维持这个 invariant:
// no missing numbers from L to M
if (M-L >= A[M] - A[L])
L = M+1;
// missing numbers are in L to M
else
H = M;
至于结束条件，这个留给大家讨论一下了 :) |
a*********0
发帖数: 2727 | 46 ...前面有人的code和你基本差不多啊，就是结束条件很烦
【在 i**********e 的大作中提到】
: 这个 binary search 就可以搞定。
: 主要就是维持这个 invariant:
: // no missing numbers from L to M
: if (M-L >= A[M] - A[L])
: L = M+1;
: // missing numbers are in L to M
: else
: H = M;
: 至于结束条件，这个留给大家讨论一下了 :)
|
i**********e
发帖数: 1145 | 47 恩，不好意思
我仔细想了想，似乎 invariant 欠缺了一些重要的东西
用lz的例子:
1 2 3 5 6
后边贴一个 +infinity，让我们的 invariant 更简洁：
1 2 3 5 6 +INF
设 lo = 0, hi = n (5) (但实际上永远不会 access A[hi])
然后再折半查找：
invariant 的条件要改一改：
if (M-L >= A[M] - A[L])
L = M;
else
H = M;
终止条件比较 tricky，就是 H - L <= 1 的时候。 |
i**********e
发帖数: 1145 | 48 不好意思，我刚看了你们之前的帖子才发现
这题对 invariant 的要求还要更深入些
我现在纸上谈兵说完了，我写个程序测试一下哈
【在 a*********0 的大作中提到】
: ...前面有人的code和你基本差不多啊，就是结束条件很烦
|
g*****k
发帖数: 623 | 49 之前都说了，判断结束是 low > high
missing number is any number in [start, end]
为了赚人品，我写下code吧，大家也指正一下。
low = 0;
high = N-1;
start = 0;
end = M-1;
while (low <= high) {
mid = low + (high - low)/2;
if (A[mid]==mid) {
low = mid + 1;
start = low;
}
else {
high = mid - 1;
end = A[mid] - 1;
}
}
//[start, end] are missing numbers, you can always return the first one.
return start;
最后如何获取结束值？好像情况很复杂
另外N应该是N-1吧，数组是0....N-1
【在 a*********0 的大作中提到】
: 最后如何获取结束值？好像情况很复杂
: 另外N应该是N-1吧，数组是0....N-1
|
i**********e
发帖数: 1145 | 50 我写了一个，测试了几个edge cases，全都 pass 了，大家参考下：
int notInArray(int A[], int n) {
int L = 0, H = n;
while (H-L > 1) {
int M = L + (H-L)/2;
assert(M >= 0 && M <= n-1);
if (M-L >= A[M]-A[L])
L = M;
else
H = M;
}
assert(L >= 0 && L <= n-1);
return A[L]+1;
} |
|
|
i**********e
发帖数: 1145 | 51 你这个 M 是什么啊？
end = M-1;
【在 g*****k 的大作中提到】
: 之前都说了，判断结束是 low > high
: missing number is any number in [start, end]
: 为了赚人品，我写下code吧，大家也指正一下。
: low = 0;
: high = N-1;
: start = 0;
: end = M-1;
: while (low <= high) {
: mid = low + (high - low)/2;
: if (A[mid]==mid) {
|
g*****k
发帖数: 623 | 52 楼主原题中说数的取值范围是0到M,
"range over M"
【在 i**********e 的大作中提到】
: 你这个 M 是什么啊？
: end = M-1;
|
g*****k
发帖数: 623 | 53 (M-L >= A[M]-A[L])
L = M;
这是错的吧。
给你举个例子
本来应该是 0,1,2,3,4,5
但是现在是 1,1,2,3,4,5
你的code会返回什么?
【在 i**********e 的大作中提到】
: 我写了一个，测试了几个edge cases，全都 pass 了，大家参考下：
: int notInArray(int A[], int n) {
: int L = 0, H = n;
: while (H-L > 1) {
: int M = L + (H-L)/2;
: assert(M >= 0 && M <= n-1);
: if (M-L >= A[M]-A[L])
: L = M;
: else
: H = M;
|
i**********e
发帖数: 1145 | 54 哦
我的解法不需要知道 range，能保证返回一个不在排序数组里面的一个值：
例如：
{1} -> 2
{1,1} -> 2
{1,2} -> 3
{1,3} -> 2
{1,2,4} -> 3
{1,3,4} -> 2
{1,2,3} -> 4
{1,1,2} -> 3
LZ 的 range over M 意思不是很清楚。真的是 0 到 M 吗？LZ 没说明数组里面的值不
能为负数。我感觉 range over M 的意思是 A[n-1] - A[0] == M ? 请 lz 解释下。
【在 g*****k 的大作中提到】
: 楼主原题中说数的取值范围是0到M,
: "range over M"
|
i**********e
发帖数: 1145 | 55 这题到底是一个还是两个序列？
发信人: absolute100 (绝对100度), 信区: JobHunting
标 题: Re: 一道G家题
发信站: BBS 未名空间站 (Thu Jul 21 18:38:53 2011, 美东)
给一个有序的M到M+N的序列，找不在这个序列中的数。要去lgn
【在 g*****k 的大作中提到】
: (M-L >= A[M]-A[L])
: L = M;
: 这是错的吧。
: 给你举个例子
: 本来应该是 0,1,2,3,4,5
: 但是现在是 1,1,2,3,4,5
: 你的code会返回什么?
|
g*****k
发帖数: 623 | 56 呵呵，原来是大家理解的不一样啊。
但是好像即便是按你理解的好像也有点不对的地方。
我们假设数组是 0,0,2,3,4,5
那么你的code似乎是返回6吧，但是如果M==5的话，就不对了。
不过题目有M>>N，所以好像不会有什么太大的问题。
其实思路是一样的。没什么本质区别。
哦
我的解法不需要知道 range，能保证返回一个不在排序数组里面的一个值：
例如：
{1} -> 2
{1,1} -> 2
{1,2} -> 3
{1,3} -> 2
{1,2,4} -> 3
{1,3,4} -> 2
{1,2,3} -> 4
{1,1,2} -> 3
LZ 的 range over M 意思不是很清楚。真的是 0 到 M 吗？LZ 没说明数组里面的值不
能为负数。我感觉 range over M 的意思是 A[n-1] - A[0] == M ? 请 lz 解释下。
【在 i**********e 的大作中提到】
: 哦
: 我的解法不需要知道 range，能保证返回一个不在排序数组里面的一个值：
: 例如：
: {1} -> 2
: {1,1} -> 2
: {1,2} -> 3
: {1,3} -> 2
: {1,2,4} -> 3
: {1,3,4} -> 2
: {1,2,3} -> 4
|
g*****k
发帖数: 623 | 57 呵呵，怀疑楼主自己都晕菜了。anyway,当练手了
【在 i**********e 的大作中提到】
: 这题到底是一个还是两个序列？
: 发信人: absolute100 (绝对100度), 信区: JobHunting
: 标 题: Re: 一道G家题
: 发信站: BBS 未名空间站 (Thu Jul 21 18:38:53 2011, 美东)
: 给一个有序的M到M+N的序列，找不在这个序列中的数。要去lgn
|
i**********e
发帖数: 1145 | 58 不错，你给的例子很好，我没测试到。
根据你的例子，应该返回的是 1,而不是 6.
这题如果可以有重复的话不可能做到 O(lg N) 吧。
【在 g*****k 的大作中提到】
: 呵呵，原来是大家理解的不一样啊。
: 但是好像即便是按你理解的好像也有点不对的地方。
: 我们假设数组是 0,0,2,3,4,5
: 那么你的code似乎是返回6吧，但是如果M==5的话，就不对了。
: 不过题目有M>>N，所以好像不会有什么太大的问题。
: 其实思路是一样的。没什么本质区别。
:
: 哦
: 我的解法不需要知道 range，能保证返回一个不在排序数组里面的一个值：
: 例如：
|
g*****k
发帖数: 623 | 59 请告知为什么这是更优的算法?
每次选数都必须做二分，也就是每次都要 lg(N)，
为什么这还是bonus？搞不懂。这题是G题吗?
good，这个实际是这题的bonus
【在 a*********0 的大作中提到】
: good，这个实际是这题的bonus
|
g*****k
发帖数: 623 | 60 如果 range over M 是指 0<=A[i]<=M, 那么我那个算法在有重复的情况下也能处理。
其实我觉得本质上我们的思路都是一样的。
【在 i**********e 的大作中提到】
: 不错，你给的例子很好，我没测试到。
: 根据你的例子，应该返回的是 1,而不是 6.
: 这题如果可以有重复的话不可能做到 O(lg N) 吧。
|
|
|
a*********0
发帖数: 2727 | 61 是G题，原题是这样
Find or determine non existence of a number in a sorted list of N numbers
where the numbers range over M, M >> N and N large enough to span multiple
disks. Algorithm to beat O(log n) bonus points for constant time algorithm
在stackoverflow上有人说用Bloom filter，所以我也没仔细想
http://stackoverflow.com/questions/3054381/find-existence-of-nu
【在 g*****k 的大作中提到】
: 请告知为什么这是更优的算法?
: 每次选数都必须做二分，也就是每次都要 lg(N)，
: 为什么这还是bonus？搞不懂。这题是G题吗?
:
: good，这个实际是这题的bonus
|
l*****e
发帖数: 1374 | 62 如果可以对N个数预处理，将其简单的存放至hashtable中，以后每次查询都可以在O(1)完成，即
M >> N的条件猜测是interviewer不想让人使用bit operation.
【在 a*********0 的大作中提到】
: Find or determine non existence of a number in a sorted list of N numbers
: where the numbers range over M, M >> N. require O(lgn)
|
w***y
发帖数: 6251 | 63 看到这个老题, 还是非常不懂啊...... 到底题目的要求是什么意思?
如果像61楼说的, 是给一个 a sorted list of N numbers ,a[N], 和a number "k".
要求找到k或者返回k不存在. N large enough to span multiple disks, 如果N很大
,前面贴的方法都不行啊, 都没办法把a[N] load到内存.
这个题目应该怎么做呢? |
