给定一个排好升序的数组A[1]、A[2]、.....、A[n],其元素的值都两两不相等,请设计一高效算法找出中间所有A[i]=i的下标。
18条回答 默认 最新
- qiemengdao 2013-09-23 20:33关注
1,这个题目中,数组A[i]应该是个整数数组
2,由升序+两两不等可知,A[i]是个递增的数列把A[i]连成一条线,则与直线y=x只有一个交点(或者有仅有一段重合),即满足:
如果A[i]>i,则点A[i]在直线y=x的上半部,即 对任意j>i,都有A[j]>j,i以后的区间可以抛弃;
如果A[i]<i,则点A[i]在直线y=x的下半部,即 对任意j<i,都有A[j]<j,i以前的区间可以抛弃;
这篇博客恰好是这个问题的完美解法:http://openmind.iteye.com/blog/1320859
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 无用评论 打赏 举报
悬赏问题
- ¥15 Pwm双极模式H桥驱动控制电机
- ¥30 这是哪个作者做的宝宝起名网站
- ¥60 版本过低apk如何修改可以兼容新的安卓系统
- ¥25 由IPR导致的DRIVER_POWER_STATE_FAILURE蓝屏
- ¥50 有数据,怎么建立模型求影响全要素生产率的因素
- ¥50 有数据,怎么用matlab求全要素生产率
- ¥15 TI的insta-spin例程
- ¥15 完成下列问题完成下列问题
- ¥15 C#算法问题, 不知道怎么处理这个数据的转换
- ¥15 YoloV5 第三方库的版本对照问题