Find Peak Element详解编程语言
A peak element is an element that is greater than its neighbors.
Given an input array where num[i] ≠ num[i+1], find a peak element and returnits index.
The array may contain multiple peaks, in that case return the index to any oneof the peaks is fine.
You may imagine that num[-1] = num[n] = -∞.
For example, in array [1, 2, 3, 1], 3 is a peak element and your functionshould return the index number 2.
Note:Your solution should be in logarithmic complexity.
由时间复杂度的暗示可知应使用二分搜索。首先分析若使用传统的二分搜索,若A[mid] A[mid - 1] A[mid] A[mid + 1],则找到一个peak为A[mid];若A[mid - 1] A[mid],则A[mid]左侧必定存在一个peak,可用反证法证明:若左侧不存在peak,则A[mid]左侧元素必满足A[0] A[1] ... A[mid -1] A[mid],与已知A[0] A[1]矛盾,证毕。同理可得若A[mid + 1] A[mid],则A[mid]右侧必定存在一个peak。如此迭代即可得解。由于题中假设端点外侧的值均为负无穷大,即num[-1] num[0] num[n-1] num[n], 那么问题来了,这样一来就不能确定峰值一定存在了,因为给定数组为单调序列的话就咩有峰值了,但是实际情况是——题中有负无穷的假设,也就是说在单调序列的情况下,峰值为数组首部或者尾部元素,谁大就是谁了。
备注:如果本题是找 first/last peak,就不能用二分法了。
class Solution { public: /** * @param A: An integers array. * @return: return any of peek positions. int findPeak(vector int A) { if (A.size() == 0) return -1; int l = 0, r = A.size() - 1; while (l + 1 r) { int mid = l + (r - l) / 2; if (A[mid] A[mid - 1]) { r = mid; } else if (A[mid] A[mid + 1]) { l = mid; } else { return mid; int mid = A[l] A[r] ? l : r; return mid; };
class Solution { /** * @param A: An integers array. * @return: return any of peek positions. public int findPeak(int[] A) { if (A == null || A.length == 0) return -1; int lb = 0, ub = A.length - 1; while (lb + 1 ub) { int mid = lb + (ub - lb) / 2; if (A[mid] A[mid + 1]) { lb = mid; } else if (A[mid] A[mid - 1]){ ub = mid; } else { // find a peak return mid; // return a larger number return A[lb] A[ub] ? lb : ub; }
典型的二分法模板应用,需要注意的是需要考虑单调序列的特殊情况。当然也可使用紧凑一点的实现如改写循环条件为l r,这样就不用考虑单调序列了,见实现2.
复杂度分析二分法,时间复杂度 O(logn).
Javapublic class Solution { public int findPeakElement(int[] nums) { if (nums == null || nums.length == 0) { return -1; int start = 0, end = nums.length - 1, mid = end / 2; while (start end) { if (nums[mid] nums[mid + 1]) { // 1 peak at least in the right side start = mid + 1; } else { // 1 peak at least in the left side end = mid; mid = start + (end - start) / 2; return start; }
原创文章,作者:ItWorker,如若转载,请注明出处:https://blog.ytso.com/20656.html
cjava相关文章
- 优化Javascript数据遍历详解编程语言
- css样式小记详解编程语言
- node中使用consolidate后报错Cannot find module ‘ejs’详解编程语言
- Struts2标签介绍详解编程语言
- hibernate12–缓存详解编程语言
- python中的Queue(队列)详解编程语言
- [javaSE] IO流(装饰设计模式)详解编程语言
- eclipse找不到 help->software update->find and install详解编程语言
- Java 多线程详解(二)——如何创建进程和线程编程语言
- Hibernate之一对多cascade,inverse详解编程语言
- java中的String字符串的常用方法详解编程语言
- 谈谈javascript中的流程控制语句详解编程语言
- 性能分析神器VisualVM详解编程语言
- HashMap源码解析详解编程语言
- 整理Python find()、Python index()和Python List index()详解编程语言
- OB52 记账期间变式和公司主数据关联关系详解编程语言
- ABAP-BarCode-2-Excel打印二维码详解编程语言
- jquery关于on click事件的理解详解编程语言
- Ubuntu下PHP动态编译出现Cannot find autoconf的解决方法详解编程语言
- Search in Rotated Sorted Array详解编程语言