s****d
发帖数: 56 | 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**********c
发帖数: 4120 | 2 [100,100,100]
needs O(n) |
h**********c
发帖数: 4120 | 3 发现不对，可以两边找
再议
【在 h**********c 的大作中提到】
: [100,100,100]
: needs O(n)
|
r****7
发帖数: 2282 | 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**********c
发帖数: 4120 | 5 log n
【在 r****7 的大作中提到】
: 没看出来有没有重复元素有啥区别啊
: 如果A[i] > i则找右边，A[i] < i则找左边，有什么问题？
:
: i]
|
s****d
发帖数: 56 | 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**********c
发帖数: 4120 | 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 的大作中提到】
: EPI中的Variant 12.3.1:
: 一个按升序排序的整数数组A，里面可以有重复元素，找出任意一个这样的i，使得A[i]
: =i, 如果不存在这样的i，返回－1.
: 没有重复元素的话比较简单，因为A[i]-i>=A[i-1]-(i-1), 这样可以binary search找
: 到0即可。
: 有重复元素的话，还能有logn的解法吗？
|
