首页 > 其他 > 详细

LeetCode(162):Find Peak Element

时间:2016-01-26 21:38:28      阅读:154      评论:0      收藏:0      [点我收藏+]

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 return its index.The array may contain multiple peaks, in that case return the index to any one of 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 function should return the index number 2.

题意:找到一个给定数组中的局部最大值,就是先递增增到最大值后然后递减,找到这个最大值,可能在这个数组中存在多个局部最大值。

思路:二分查找。如果中间元素大于其相邻的后序元素,则中间元素左侧比包含一个局部最大值。如果中间元素小于其相邻后序元素,则中间元素右侧必包含一个局部最大值。直到最左边和最右边相遇。

代码:

public int findPeakElement(int[] nums) {
        int len = nums.length;
            if(len==1) return 0;
            int left =0,right=len-1;
             while(left<=right){
                 if (left==right) return left;
                 int mid = (left+right) /2 ;
                 if(nums[mid] <nums[mid+1]){
                     left = mid + 1;
                 }else{
                     right = mid;
                 }
             }
             return -1;
    }

LeetCode(162):Find Peak Element

原文:http://www.cnblogs.com/Lewisr/p/5161491.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!