问EPI一题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

问EPI一题

问EPI一题# JobHunting - 待字闺中

s*d2015-01-04 08:01

1 楼

EPI中的Variant 12.3.1:
一个按升序排序的整数数组A，里面可以有重复元素，找出任意一个这样的i，使得A[i]
=i, 如果不存在这样的i，返回－1.
没有重复元素的话比较简单，因为A[i]-i>=A[i-1]-(i-1), 这样可以binary search找
到0即可。
有重复元素的话，还能有logn的解法吗？

h*c2015-01-04 08:01

2 楼

[100,100,100]
needs O(n)

h*c2015-01-04 08:01

3 楼

发现不对，可以两边找
再议

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

: [100,100,100]
: needs O(n)

r*72015-01-04 08:01

4 楼

没看出来有没有重复元素有啥区别啊
如果A[i] > i则找右边，A[i] < i则找左边，有什么问题？

i]

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

: EPI中的Variant 12.3.1:
: 一个按升序排序的整数数组A，里面可以有重复元素，找出任意一个这样的i，使得A[i]
: =i, 如果不存在这样的i，返回－1.
: 没有重复元素的话比较简单，因为A[i]-i>=A[i-1]-(i-1), 这样可以binary search找
: 到0即可。
: 有重复元素的话，还能有logn的解法吗？

h*c2015-01-04 08:01

5 楼

log n

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

: 没看出来有没有重复元素有啥区别啊
: 如果A[i] > i则找右边，A[i] < i则找左边，有什么问题？
:
: i]

s*d2015-01-04 08:01

6 楼

>>如果A[i] > i则找右边，A[i] < i则找左边，有什么问题？
。。，这没有重复元素都不work
-2 0 1 3 6
A[2]=1 < 2，找左边？
关键问题是有重复元素的时候 A[i] -i序列不是递增的，在重复元素处会递减，
binary search找0就不work了

h*c2015-01-04 08:01

7 楼

if we can prove a_i = i can happen at any position,
then log n is not possible.
So we can construct n arrays.
For the i-th array
a_i = i, any element less than a_i differ differ by -2 sequentially, bigger
differ by 2
You won't have ONE log n algorithm to deal with all the above mentioned
arrays.

i]

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