LeetCode算法题-Peak Index in a Mountain Array(Java实现)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode算法题-Peak Index in a Mountain Array(Java实现),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2131字,纯文字阅读大概需要4分钟。
内容图文
![LeetCode算法题-Peak Index in a Mountain Array(Java实现)](/upload/InfoBanner/zyjiaocheng/829/2219bb6e0f9b43e18a9eb5439401915d.jpg)
这是悦乐书的第329次更新,第352篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第199题(顺位题号是852)。如果以下属性成立,我们将数组A称为山:
A.length> = 3。
存在一个i(0 < i < A.length-1),使得A[0] <A[1] <... A[i-1] < A[i] > A[i + 1]> ...> A[A.length - 1]。
给定一个绝对是山的数组,返回i,使得A[0] <A[1] <... A[i-1] <A[i]> A[i + 1]> ...> A [A.length - 1]。例如:
输入:[0,1,0]
输出:1
输入:[0,2,1,0]
输出:1
注意:
3 <= A.length <= 10000
0 <= A [i] <= 10 ^ 6
如上所述,A是一座山。
本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。
02 第一种解法
数组A是座山的意思是指,数组A中的元素大小排列像山的形状一样,由低处到山顶,再由山顶到低处,而题目要求我们找的那个i就是山顶所在位置的索引,而题目给出的条件是,数组A肯定是一座山,所以可以直接使用遍历数组元素的方式,从第一位元素开始,往后比较,小于就继续往后,直到当前元素大于它的后一个元素,表示此元素就是山顶了,直接返回该元素索引即可。
public int peakIndexInMountainArray(int[] A) {
int n = A.length;
for (int i=0; i<n-1; i++) {
if (A[i] < A[i+1]) {
continue;
} else {
return i;
}
}
return 0;
}
03 第二种解法
思路和上面一样,也是直接遍历数组元素,进行比较,找到山顶。
public int peakIndexInMountainArray(int[] A) {
int index = 0;
while (A[index] < A[index+1]) {
index++;
}
return index;
}
03 第三种解法
上面两种解法的时间复杂度都是O(N),我们还可以使用二分查找法,将时间复杂度降低为O(logN)。定义两个变量left、right,一个从0开始,一个从数组最后一位开始,每次取两者中间值,得到该中间位置的元素,然后和它的前一个元素比较大小,如果小于,说明还没有到山顶,需要继续向前,将中间值加1后赋值给left,反之就将中间值赋值给right。循环结束的条件是left不小于right,最后返回left即可。
public int peakIndexInMountainArray(int[] A) {
int left = 0, right = A.length-1;
while (left < right) {
int mid = left + (right-left)/2;
if (A[mid] < A[mid+1]) {
left = mid+1;
} else {
right = mid;
}
}
return left;
}
04 小结
算法专题目前已日更超过五个月,算法题文章199+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。
以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!
内容总结
以上是互联网集市为您收集整理的LeetCode算法题-Peak Index in a Mountain Array(Java实现)全部内容,希望文章能够帮你解决LeetCode算法题-Peak Index in a Mountain Array(Java实现)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。