没见过这么笨这么杯具的贼，哈哈，真好笑！ (转载) - 未名空间MITBBS历史存档

没见过这么笨这么杯具的贼，哈哈，真好笑！ (转载)# Joke - 肚皮舞运动

N*g2011-10-11 07:10

1 楼

☆─────────────────────────────────────☆
Z12 (神医是怎样练成的？) 于 (Sun Jun 28 09:33:33 2009, 美东) 提到:
☆─────────────────────────────────────☆
uthinkmumu (ding) 于 (Sun Jun 28 09:37:02 2009, 美东) 提到:
deal死
hoho

☆─────────────────────────────────────☆
oceanview (oceanview) 于 (Sun Jun 28 11:57:50 2009, 美东) 提到:
80 off 99% will get canceled.

i*n2011-10-11 07:10

2 楼

find the longest run number within a sorted array.
For example:
1,1,1,2,2,2,2,6,8,8,8,8,8,8,8,8,9
the longest long number is 8
do it with O(log(n)), constant space.

B*e2011-10-11 07:10

3 楼

【以下文字转载自 WaterWorld 讨论区】
发信人: gooddays (开心每一天), 信区: WaterWorld
标题: 没见过这么笨这么杯具的贼，哈哈，真好笑！
发信站: BBS 未名空间站 (Mon Oct 10 23:08:20 2011, 美东)
盗窃不成反被困四日后饿晕被擒。。。

w*t2011-10-11 07:10

4 楼

Find the majority element since no specific element is provided.
Use Moore's voting algorithm:
1. Find the majority
2. Verify the majority (we can skip this step for this question.)

【在 i******n 的大作中提到】

: find the longest run number within a sorted array.
: For example:
: 1,1,1,2,2,2,2,6,8,8,8,8,8,8,8,8,9
: the longest long number is 8
: do it with O(log(n)), constant space.

a*e2011-10-11 07:10

5 楼

小姑娘真好人啊，还带他去吃面

w*t2011-10-11 07:10

6 楼

想起来这个需要O(n)。
用binary search的话，需要知道找哪个element啊？

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

: Find the majority element since no specific element is provided.
: Use Moore's voting algorithm:
: 1. Find the majority
: 2. Verify the majority (we can skip this step for this question.)

K*s2011-10-11 07:10

7 楼

这事放美国小偷就能告死屋主了

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

: 【以下文字转载自 WaterWorld 讨论区】
: 发信人: gooddays (开心每一天), 信区: WaterWorld
: 标题: 没见过这么笨这么杯具的贼，哈哈，真好笑！
: 发信站: BBS 未名空间站 (Mon Oct 10 23:08:20 2011, 美东)
: 盗窃不成反被困四日后饿晕被擒。。。

i*n2011-10-11 07:10

8 楼

Thank you.
first it's linear, second it's wrong to apply to this question. The majority
means more than half.

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

: Find the majority element since no specific element is provided.
: Use Moore's voting algorithm:
: 1. Find the majority
: 2. Verify the majority (we can skip this step for this question.)

h*02011-10-11 07:10

9 楼

为啥？屋主有过错吗？

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

: 这事放美国小偷就能告死屋主了

s*n2011-10-11 07:10

10 楼

O(log(n))可能吗？

R*a2011-10-11 07:10

11 楼

这个就看律师嘴有多厉害了

【在 h*****0 的大作中提到】

: 为啥？屋主有过错吗？

w*t2011-10-11 07:10

12 楼

是的。不过第一个可以找出出现次数最多的element。

majority

【在 i******n 的大作中提到】

: Thank you.
: first it's linear, second it's wrong to apply to this question. The majority
: means more than half.

h*02011-10-11 07:10

13 楼

只要这个门的安装本身是合活的就没问题。

【在 R***a 的大作中提到】

: 这个就看律师嘴有多厉害了

S*w2011-10-11 07:10

14 楼

findmax(int A[], int i, int j){
find the range of A[(i+j)/2] using binary search, say is [p, q]
return max(findmax(A,i, p-1), p-q+1, findmax(A, q+1, j))
}

【在 i******n 的大作中提到】

: find the longest run number within a sorted array.
: For example:
: 1,1,1,2,2,2,2,6,8,8,8,8,8,8,8,8,9
: the longest long number is 8
: do it with O(log(n)), constant space.

K*s2011-10-11 07:10

15 楼

在美国有个小偷从车库跳进一家去偷东西，结果不但进不去房间，还从里面打不开车库
门。适逢holiday season, 在车库里苦熬多日才重见天日。愤而把屋主告了，拿了一
笔赔偿。

【在 h*****0 的大作中提到】

: 为啥？屋主有过错吗？

r*t2011-10-11 07:10

16 楼

log(N)^2?

【在 S*******w 的大作中提到】

: findmax(int A[], int i, int j){
: find the range of A[(i+j)/2] using binary search, say is [p, q]
: return max(findmax(A,i, p-1), p-q+1, findmax(A, q+1, j))
: }

S*w2011-10-11 07:10

17 楼

I am not sure it is O(log n) or (log^2n)
more analysis needed

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

: log(N)^2?

q*x2011-10-11 07:10

18 楼

yet another fake question from careercup site?

【在 i******n 的大作中提到】

: find the longest run number within a sorted array.
: For example:
: 1,1,1,2,2,2,2,6,8,8,8,8,8,8,8,8,9
: the longest long number is 8
: do it with O(log(n)), constant space.

e*s2011-10-11 07:10

19 楼

这个O(n)就很弱智了，O(log(n))又很难

i*n2011-10-11 07:10

20 楼

No just got interviewed.

【在 q****x 的大作中提到】

: yet another fake question from careercup site?

i*n2011-10-11 07:10

21 楼

I mentioned your method, but it doesn't met requirement

【在 S*******w 的大作中提到】

: findmax(int A[], int i, int j){
: find the range of A[(i+j)/2] using binary search, say is [p, q]
: return max(findmax(A,i, p-1), p-q+1, findmax(A, q+1, j))
: }

a*m2011-10-11 07:10

22 楼

lg(n)似乎不可能。如果数组是1,2,3,4,5,6,7.....n. 看不出来哪个元素可以跳过。

i*n2011-10-11 07:10

23 楼

I mentioned to compare the begin with mid value and the index difference.

【在 a********m 的大作中提到】

: lg(n)似乎不可能。如果数组是1,2,3,4,5,6,7.....n. 看不出来哪个元素可以跳过。

r*12011-10-11 07:10

24 楼

good point.

【在 a********m 的大作中提到】

: lg(n)似乎不可能。如果数组是1,2,3,4,5,6,7.....n. 看不出来哪个元素可以跳过。

q*c2011-10-11 07:10

25 楼

This is a variant of binary search. Idea:
Compare the middle item with both item[0] and item[n-1]
return the number that is equal to either one of them.
recursively do this process in both left and right subarray.

H*e2011-10-11 07:10

26 楼

logn 每次要丢掉一半
11111233333
没有办法判断丢掉哪一半吧

【在 i******n 的大作中提到】

: find the longest run number within a sorted array.
: For example:
: 1,1,1,2,2,2,2,6,8,8,8,8,8,8,8,8,9
: the longest long number is 8
: do it with O(log(n)), constant space.

j*j2011-10-11 07:10

27 楼

recursive必定要用非consistent空间，要写成iterative的

【在 q********c 的大作中提到】

: This is a variant of binary search. Idea:
: Compare the middle item with both item[0] and item[n-1]
: return the number that is equal to either one of them.
: recursively do this process in both left and right subarray.

j*j2011-10-11 07:10

28 楼

worst case必须O(n)吧，average logn就行

【在 a********m 的大作中提到】

: lg(n)似乎不可能。如果数组是1,2,3,4,5,6,7.....n. 看不出来哪个元素可以跳过。

a*m2011-10-11 07:10

29 楼

感觉还是不对。能省略某个branch计算的情况比较少，不需要worst case。 general
case就少。似乎只能通过二分法优化掉一些分支，但是不降低整体复杂度.

【在 j*****j 的大作中提到】

: worst case必须O(n)吧，average logn就行

q*c2011-10-11 07:10

30 楼

worst case 2log(n) because unlike the standard binary search you do it both
branches.

d*o2011-10-11 07:10

31 楼

反例：
1 1 1 2 2 2 2 3 3 3

【在 q********c 的大作中提到】

: This is a variant of binary search. Idea:
: Compare the middle item with both item[0] and item[n-1]
: return the number that is equal to either one of them.
: recursively do this process in both left and right subarray.

H*s2011-10-11 07:10

32 楼

If you do both branches, that is O(n) not 2log(n)
How can log(n) be possible?
eq. 0 1 2 3 4 ... 10 11 11 13 ... INT_MAX-1

both

【在 q********c 的大作中提到】

: worst case 2log(n) because unlike the standard binary search you do it both
: branches.

w*g2011-10-11 07:10

33 楼

可以证明最长出现次数K小于一定大小的话无法用O(log n)解，如下：
假设算法复杂度< Clog(n), C为任意常数。
Clog(n)的算法最多只能看到整个数列中Clog(n)个数。也就是说剩下的n-Clog(n)个数，
只要顺序不和已经看到的Clog(n)个数冲突，可以随便改，不会影响算法的输出。看到的
那些数把整个序列分成Clog(n)+1个区间，所以必有一个区间的会比 m = (n-Clog(n))/
(Clog(n)+1)大。令K = 1/3 m，那么所有长度大于m的区间两个端点的值都不可能一样
，而且中间还有第三个值(否则最长出现的次数就大于K了）。考虑任意一个这样的区间
。不管算法给出的预测是否包含这个区间的端点，都可以通过修改该区间中间的数字使
得该数字出现K次，也就是最多次。这样算法给出的预测至少就不是唯一的了。K的值在
～1/3n/Clog(n)，当n大的时候可以很大。
好吧，我比较无聊。

【在 i******n 的大作中提到】

: find the longest run number within a sorted array.
: For example:
: 1,1,1,2,2,2,2,6,8,8,8,8,8,8,8,8,9
: the longest long number is 8
: do it with O(log(n)), constant space.

H*s2011-10-11 07:10

34 楼

有道理！

数，
到的
)/

【在 w***g 的大作中提到】

: 可以证明最长出现次数K小于一定大小的话无法用O(log n)解，如下：
: 假设算法复杂度< Clog(n), C为任意常数。
: Clog(n)的算法最多只能看到整个数列中Clog(n)个数。也就是说剩下的n-Clog(n)个数，
: 只要顺序不和已经看到的Clog(n)个数冲突，可以随便改，不会影响算法的输出。看到的
: 那些数把整个序列分成Clog(n)+1个区间，所以必有一个区间的会比 m = (n-Clog(n))/
: (Clog(n)+1)大。令K = 1/3 m，那么所有长度大于m的区间两个端点的值都不可能一样
: ，而且中间还有第三个值(否则最长出现的次数就大于K了）。考虑任意一个这样的区间
: 。不管算法给出的预测是否包含这个区间的端点，都可以通过修改该区间中间的数字使
: 得该数字出现K次，也就是最多次。这样算法给出的预测至少就不是唯一的了。K的值在
: ～1/3n/Clog(n)，当n大的时候可以很大。

S*w2011-10-11 07:10

35 楼

高手就是不一样！

数，
到的
)/

【在 w***g 的大作中提到】

: 可以证明最长出现次数K小于一定大小的话无法用O(log n)解，如下：
: 假设算法复杂度< Clog(n), C为任意常数。
: Clog(n)的算法最多只能看到整个数列中Clog(n)个数。也就是说剩下的n-Clog(n)个数，
: 只要顺序不和已经看到的Clog(n)个数冲突，可以随便改，不会影响算法的输出。看到的
: 那些数把整个序列分成Clog(n)+1个区间，所以必有一个区间的会比 m = (n-Clog(n))/
: (Clog(n)+1)大。令K = 1/3 m，那么所有长度大于m的区间两个端点的值都不可能一样
: ，而且中间还有第三个值(否则最长出现的次数就大于K了）。考虑任意一个这样的区间
: 。不管算法给出的预测是否包含这个区间的端点，都可以通过修改该区间中间的数字使
: 得该数字出现K次，也就是最多次。这样算法给出的预测至少就不是唯一的了。K的值在
: ～1/3n/Clog(n)，当n大的时候可以很大。

p*22011-10-11 07:10

36 楼

说了半天就是一个废题？

i*n2011-10-11 07:10

37 楼

i see, but it's actually asked by a google interviewer. And it takes me a
long time...

数，
到的
)/

【在 w***g 的大作中提到】

: 可以证明最长出现次数K小于一定大小的话无法用O(log n)解，如下：
: 假设算法复杂度< Clog(n), C为任意常数。
: Clog(n)的算法最多只能看到整个数列中Clog(n)个数。也就是说剩下的n-Clog(n)个数，
: 只要顺序不和已经看到的Clog(n)个数冲突，可以随便改，不会影响算法的输出。看到的
: 那些数把整个序列分成Clog(n)+1个区间，所以必有一个区间的会比 m = (n-Clog(n))/
: (Clog(n)+1)大。令K = 1/3 m，那么所有长度大于m的区间两个端点的值都不可能一样
: ，而且中间还有第三个值(否则最长出现的次数就大于K了）。考虑任意一个这样的区间
: 。不管算法给出的预测是否包含这个区间的端点，都可以通过修改该区间中间的数字使
: 得该数字出现K次，也就是最多次。这样算法给出的预测至少就不是唯一的了。K的值在
: ～1/3n/Clog(n)，当n大的时候可以很大。

w*n2011-10-11 07:10

38 楼

装继续装

【在 i******n 的大作中提到】

: i see, but it's actually asked by a google interviewer. And it takes me a
: long time...
:
: 数，
: 到的
: )/

i*n2011-10-11 07:10

39 楼

I appreciate those persons who help me to figure out what happened but what
you said really makes me disappointed.

【在 w******n 的大作中提到】

: 装继续装

l*y2011-10-11 07:10

40 楼

这个应该是O(n)复杂度吧

【在 S*******w 的大作中提到】

: findmax(int A[], int i, int j){
: find the range of A[(i+j)/2] using binary search, say is [p, q]
: return max(findmax(A,i, p-1), p-q+1, findmax(A, q+1, j))
: }

i*n2011-10-11 07:10

41 楼

find the longest run number within a sorted array.
For example:
1,1,1,2,2,2,2,6,8,8,8,8,8,8,8,8,9
the longest long number is 8
do it with O(log(n)), constant space.

w*t2011-10-11 07:10

42 楼

Find the majority element since no specific element is provided.
Use Moore's voting algorithm:
1. Find the majority
2. Verify the majority (we can skip this step for this question.)

【在 i******n 的大作中提到】

: find the longest run number within a sorted array.
: For example:
: 1,1,1,2,2,2,2,6,8,8,8,8,8,8,8,8,9
: the longest long number is 8
: do it with O(log(n)), constant space.

w*t2011-10-11 07:10

43 楼

想起来这个需要O(n)。
用binary search的话，需要知道找哪个element啊？

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

: Find the majority element since no specific element is provided.
: Use Moore's voting algorithm:
: 1. Find the majority
: 2. Verify the majority (we can skip this step for this question.)

i*n2011-10-11 07:10

44 楼

Thank you.
first it's linear, second it's wrong to apply to this question. The majority
means more than half.

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

: Find the majority element since no specific element is provided.
: Use Moore's voting algorithm:
: 1. Find the majority
: 2. Verify the majority (we can skip this step for this question.)

s*n2011-10-11 07:10

45 楼

O(log(n))可能吗？

w*t2011-10-11 07:10

46 楼

是的。不过第一个可以找出出现次数最多的element。

majority

【在 i******n 的大作中提到】

: Thank you.
: first it's linear, second it's wrong to apply to this question. The majority
: means more than half.

S*w2011-10-11 07:10

47 楼

findmax(int A[], int i, int j){
find the range of A[(i+j)/2] using binary search, say is [p, q]
return max(findmax(A,i, p-1), p-q+1, findmax(A, q+1, j))
}

【在 i******n 的大作中提到】

: find the longest run number within a sorted array.
: For example:
: 1,1,1,2,2,2,2,6,8,8,8,8,8,8,8,8,9
: the longest long number is 8
: do it with O(log(n)), constant space.

r*t2011-10-11 07:10

48 楼

log(N)^2?

【在 S*******w 的大作中提到】

: findmax(int A[], int i, int j){
: find the range of A[(i+j)/2] using binary search, say is [p, q]
: return max(findmax(A,i, p-1), p-q+1, findmax(A, q+1, j))
: }

S*w2011-10-11 07:10

49 楼

I am not sure it is O(log n) or (log^2n)
more analysis needed

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

: log(N)^2?

q*x2011-10-11 07:10

50 楼

yet another fake question from careercup site?

【在 i******n 的大作中提到】

: find the longest run number within a sorted array.
: For example:
: 1,1,1,2,2,2,2,6,8,8,8,8,8,8,8,8,9
: the longest long number is 8
: do it with O(log(n)), constant space.

e*s2011-10-11 07:10

51 楼

这个O(n)就很弱智了，O(log(n))又很难

i*n2011-10-11 07:10

52 楼

No just got interviewed.

【在 q****x 的大作中提到】

: yet another fake question from careercup site?

i*n2011-10-11 07:10

53 楼

I mentioned your method, but it doesn't met requirement

【在 S*******w 的大作中提到】

: findmax(int A[], int i, int j){
: find the range of A[(i+j)/2] using binary search, say is [p, q]
: return max(findmax(A,i, p-1), p-q+1, findmax(A, q+1, j))
: }

a*m2011-10-11 07:10

54 楼

lg(n)似乎不可能。如果数组是1,2,3,4,5,6,7.....n. 看不出来哪个元素可以跳过。

i*n2011-10-11 07:10

55 楼

I mentioned to compare the begin with mid value and the index difference.

【在 a********m 的大作中提到】

: lg(n)似乎不可能。如果数组是1,2,3,4,5,6,7.....n. 看不出来哪个元素可以跳过。

r*12011-10-11 07:10

56 楼

good point.

【在 a********m 的大作中提到】

: lg(n)似乎不可能。如果数组是1,2,3,4,5,6,7.....n. 看不出来哪个元素可以跳过。

q*c2011-10-11 07:10

57 楼

This is a variant of binary search. Idea:
Compare the middle item with both item[0] and item[n-1]
return the number that is equal to either one of them.
recursively do this process in both left and right subarray.

H*e2011-10-11 07:10

58 楼

logn 每次要丢掉一半
11111233333
没有办法判断丢掉哪一半吧

【在 i******n 的大作中提到】

: find the longest run number within a sorted array.
: For example:
: 1,1,1,2,2,2,2,6,8,8,8,8,8,8,8,8,9
: the longest long number is 8
: do it with O(log(n)), constant space.

j*j2011-10-11 07:10

59 楼

recursive必定要用非consistent空间，要写成iterative的

【在 q********c 的大作中提到】

: This is a variant of binary search. Idea:
: Compare the middle item with both item[0] and item[n-1]
: return the number that is equal to either one of them.
: recursively do this process in both left and right subarray.

j*j2011-10-11 07:10

60 楼

worst case必须O(n)吧，average logn就行

【在 a********m 的大作中提到】

: lg(n)似乎不可能。如果数组是1,2,3,4,5,6,7.....n. 看不出来哪个元素可以跳过。

a*m2011-10-11 07:10

61 楼

感觉还是不对。能省略某个branch计算的情况比较少，不需要worst case。 general
case就少。似乎只能通过二分法优化掉一些分支，但是不降低整体复杂度.

【在 j*****j 的大作中提到】

: worst case必须O(n)吧，average logn就行

q*c2011-10-11 07:10

62 楼

worst case 2log(n) because unlike the standard binary search you do it both
branches.

d*o2011-10-11 07:10

63 楼

反例：
1 1 1 2 2 2 2 3 3 3

【在 q********c 的大作中提到】

: This is a variant of binary search. Idea:
: Compare the middle item with both item[0] and item[n-1]
: return the number that is equal to either one of them.
: recursively do this process in both left and right subarray.

H*s2011-10-11 07:10

64 楼

If you do both branches, that is O(n) not 2log(n)
How can log(n) be possible?
eq. 0 1 2 3 4 ... 10 11 11 13 ... INT_MAX-1

both

【在 q********c 的大作中提到】

: worst case 2log(n) because unlike the standard binary search you do it both
: branches.

w*g2011-10-11 07:10

65 楼

可以证明最长出现次数K小于一定大小的话无法用O(log n)解，如下：
假设算法复杂度< Clog(n), C为任意常数。
Clog(n)的算法最多只能看到整个数列中Clog(n)个数。也就是说剩下的n-Clog(n)个数，
只要顺序不和已经看到的Clog(n)个数冲突，可以随便改，不会影响算法的输出。看到的
那些数把整个序列分成Clog(n)+1个区间，所以必有一个区间的会比 m = (n-Clog(n))/
(Clog(n)+1)大。令K = 1/3 m，那么所有长度大于m的区间两个端点的值都不可能一样
，而且中间还有第三个值(否则最长出现的次数就大于K了）。考虑任意一个这样的区间
。不管算法给出的预测是否包含这个区间的端点，都可以通过修改该区间中间的数字使
得该数字出现K次，也就是最多次。这样算法给出的预测至少就不是唯一的了。K的值在
～1/3n/Clog(n)，当n大的时候可以很大。
好吧，我比较无聊。

【在 i******n 的大作中提到】

: find the longest run number within a sorted array.
: For example:
: 1,1,1,2,2,2,2,6,8,8,8,8,8,8,8,8,9
: the longest long number is 8
: do it with O(log(n)), constant space.

H*s2011-10-11 07:10

66 楼

有道理！

数，
到的
)/

【在 w***g 的大作中提到】

: 可以证明最长出现次数K小于一定大小的话无法用O(log n)解，如下：
: 假设算法复杂度< Clog(n), C为任意常数。
: Clog(n)的算法最多只能看到整个数列中Clog(n)个数。也就是说剩下的n-Clog(n)个数，
: 只要顺序不和已经看到的Clog(n)个数冲突，可以随便改，不会影响算法的输出。看到的
: 那些数把整个序列分成Clog(n)+1个区间，所以必有一个区间的会比 m = (n-Clog(n))/
: (Clog(n)+1)大。令K = 1/3 m，那么所有长度大于m的区间两个端点的值都不可能一样
: ，而且中间还有第三个值(否则最长出现的次数就大于K了）。考虑任意一个这样的区间
: 。不管算法给出的预测是否包含这个区间的端点，都可以通过修改该区间中间的数字使
: 得该数字出现K次，也就是最多次。这样算法给出的预测至少就不是唯一的了。K的值在
: ～1/3n/Clog(n)，当n大的时候可以很大。

S*w2011-10-11 07:10

67 楼

高手就是不一样！

数，
到的
)/

【在 w***g 的大作中提到】

: 可以证明最长出现次数K小于一定大小的话无法用O(log n)解，如下：
: 假设算法复杂度< Clog(n), C为任意常数。
: Clog(n)的算法最多只能看到整个数列中Clog(n)个数。也就是说剩下的n-Clog(n)个数，
: 只要顺序不和已经看到的Clog(n)个数冲突，可以随便改，不会影响算法的输出。看到的
: 那些数把整个序列分成Clog(n)+1个区间，所以必有一个区间的会比 m = (n-Clog(n))/
: (Clog(n)+1)大。令K = 1/3 m，那么所有长度大于m的区间两个端点的值都不可能一样
: ，而且中间还有第三个值(否则最长出现的次数就大于K了）。考虑任意一个这样的区间
: 。不管算法给出的预测是否包含这个区间的端点，都可以通过修改该区间中间的数字使
: 得该数字出现K次，也就是最多次。这样算法给出的预测至少就不是唯一的了。K的值在
: ～1/3n/Clog(n)，当n大的时候可以很大。

p*22011-10-11 07:10

68 楼

说了半天就是一个废题？

i*n2011-10-11 07:10

69 楼

i see, but it's actually asked by a google interviewer. And it takes me a
long time...

数，
到的
)/

【在 w***g 的大作中提到】

: 可以证明最长出现次数K小于一定大小的话无法用O(log n)解，如下：
: 假设算法复杂度< Clog(n), C为任意常数。
: Clog(n)的算法最多只能看到整个数列中Clog(n)个数。也就是说剩下的n-Clog(n)个数，
: 只要顺序不和已经看到的Clog(n)个数冲突，可以随便改，不会影响算法的输出。看到的
: 那些数把整个序列分成Clog(n)+1个区间，所以必有一个区间的会比 m = (n-Clog(n))/
: (Clog(n)+1)大。令K = 1/3 m，那么所有长度大于m的区间两个端点的值都不可能一样
: ，而且中间还有第三个值(否则最长出现的次数就大于K了）。考虑任意一个这样的区间
: 。不管算法给出的预测是否包含这个区间的端点，都可以通过修改该区间中间的数字使
: 得该数字出现K次，也就是最多次。这样算法给出的预测至少就不是唯一的了。K的值在
: ～1/3n/Clog(n)，当n大的时候可以很大。

i*n2011-10-11 07:10

70 楼

I appreciate those persons who help me to figure out what happened but what
you said really makes me disappointed.

【在 w******n 的大作中提到】

: 装继续装

l*y2011-10-11 07:10

71 楼

这个应该是O(n)复杂度吧

【在 S*******w 的大作中提到】

: findmax(int A[], int i, int j){
: find the range of A[(i+j)/2] using binary search, say is [p, q]
: return max(findmax(A,i, p-1), p-q+1, findmax(A, q+1, j))
: }

h*22011-10-11 07:10

72 楼

还是没有看到有logN的解法，呼唤大牛解答...

n*w2011-10-11 07:10

73 楼

如果both branches都要do，那就是O(n)，而不是2logN。
logN必须每次丢掉一半。

both

【在 q********c 的大作中提到】

: worst case 2log(n) because unlike the standard binary search you do it both
: branches.

w*x2011-10-11 07:10

74 楼

logn能做出来我从布瑞温楼顶上跳下去