E*******F
发帖数: 2165 | 1 一个非降序排列的整数数组A（可以有重复元素），找出A[i]=i的第一个元素（使i尽可
能小）
优化的算法是什么 |
C***U
发帖数: 2406 | 2 binary search 应该可以。 但是最坏情况的时候还是O(n)
【在 E*******F 的大作中提到】
: 一个非降序排列的整数数组A（可以有重复元素），找出A[i]=i的第一个元素（使i尽可
: 能小）
: 优化的算法是什么
|
K****n
发帖数: 5970 | 3 这其实是一个几何问题
一条直线 y=x
一条单调非增曲线y=f(x)
问所有交点的x坐标最小是啥
可以发挥一下空间想象力 |
c****p
发帖数: 6474 | 4 原题是单调非减，，，，y=f(x)的截距不一定为零啊，，，，而且交点可以很多的。。。
【在 K****n 的大作中提到】
: 这其实是一个几何问题
: 一条直线 y=x
: 一条单调非增曲线y=f(x)
: 问所有交点的x坐标最小是啥
: 可以发挥一下空间想象力
|
K****n
发帖数: 5970 | 5 我想的是非减，所以俺没说有小于O(N）的解法，空间想象力是看有没有人能顺着找到
logN之类的办法。
不知道为神马打成了非增，非增是简单了些。
。。
【在 c****p 的大作中提到】
: 原题是单调非减，，，，y=f(x)的截距不一定为零啊，，，，而且交点可以很多的。。。
|
