问题:
给定一个数组,其值先从小到大递增后从大到小递减,找出最大的值。
思路:最简单的办法就是从第二个值开始,判断是否满足 A[i] > A[i-1] && A[i] > A[i+1]. 如果满足,i 就是那个最大值的下标。该算法复杂度为O(n).
我们可以改进这种算法,因为这个数组是排好序的,所以我们可以利用二分查找的思想,更快速的找到最大值,时间复杂度为O(lg n)。
二分查找的算法可以在后面的link处得到,二分查找的退出条件和这道题的退出条件是不一样的(详见while loop),这是很值得注意的地方。
http://blog.csdn.net/beiyeqingteng/article/details/5736004
public int turningPoint(int[] A) {
int m = A.length;
int begin = 0;
int end = m - 1;
int tp = begin + (end - begin)/2;
// the condition "tp > 0 && tp < m -1" makes sure that tp is not at the beginning or the end
while (tp > 0 && tp < m -1) {
if (A[tp] > A[tp + 1] && A[tp] > A[tp -1]) {
return tp;
} else if (A[tp] < A[tp+1]) {
begin = tp + 1;
tp = begin + (end - begin)/2;
} else {
end = tp - 1;
tp = begin + (end - begin)/2;
}
}
return -1;
}
分享到:
相关推荐
1.5.8. 给出一个数列,找出其中最长的单调递减(或递增)子序列..............121 1.5.9. 四对括号可以有多少种匹配排列方式.................................................124 1.5.10. 输入一个正数 n,输出...
在一个数组中找出连续元素的最大值,时间复杂度o(n),空间复杂度o(n)
java 数组递增排序 java 数组递增排序 java 数组递增排序
一个长度为100的数组,开始乱序存放了1到100共100个数, 将其中一个位置上面的数字赋值为-1,请问该位置赋值之前是多少? 一个长度为100的数组,开始乱序存放了1到100共100个数, 将其中两个位置上面的数字赋值为-1...
java 部分数组递增排序 java 部分数组递增排序 java 部分数组递增排序
labview小程序,将一个二维数组中的每一行都加一个递增的数
判断数据递增的方法,递归算法,简单明了 快速高效
两个递增有序的单链表合并成一个递减有序的.cpp
* 数 组 -----数组的概念与定义 课程内容 数组的概念 数组的定义 一、数组的概念 假如要存储一个班学生的成绩,如果使用变量来存储成绩,就需要定义多个变量,显然这个定义的过程相当耗费时间与精力,PHP语言提供了...
js代码-(算法)(数组)先升后降数组找最大值
判断字符串或者密码是不是连续递增的如1234567 7654321 abcdefg 之类的
对一个含有N整数的数组,使用堆排序让其由小到大输出 样例输入 6 43 2 56 1 22 9 样例输出 1 2 9 22 43 56 堆排序 对一个含有N整数的数组,使用堆排序让其由小到大输出 样例输入 6 43 2 56 1 22 9 样例输出 1 2 9 ...
android视图,其值可以递增或递减一。
从键盘输入两个链表,通过程序对他们排序,之后按递增顺序合并链表
C语言的数组 排序,删除,查找联合搬算法
易语言源码易语言快速数组类源码.rar
两个升序的数组A、B,将AB合并到C,保持升序,去除重生的元素
该算法为将两个递增的链表合并为一个递减链表,采用头插法和尾插法两种不同的方法实现
initVal:step:endVal - 每次迭代时按值 step 对 index 进行递增,或在 step 是负数时对 index 进行递减。 valArray - 每次迭代时从数组 valArray 的后续列创建列向量 index。例如,在第一次迭代时,index = ...