欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode----162. Find Peak Element

程序员文章站 2022-06-17 18:33:53
...

链接:

https://leetcode.com/problems/find-peak-element/

大意:

返回一个数组的峰顶值所在的位置。一个数组的峰顶值:该值大于其左右两边相邻的两个元素。规定:nums[0]左边和nums[nums.length - 1]右边可以认为是Integer.MIN_VALUE。例子:

leetcode----162. Find Peak Element

思路:

顺序遍历,找到第一个降序的点即可。

代码:

class Solution {
    public int findPeakElement(int[] nums) {
        if (nums.length <= 1)
            return 0;
        int i = 0;
        // 找到第一个降序的点
        while (i + 1 < nums.length && nums[i] < nums[i + 1]) {
            i++;
        }
        return i == nums.length ? i - 1 : i;
    }
}

结果:

leetcode----162. Find Peak Element

结论:

刚才又认真地看了遍题目,说是最好用对数复杂度解决,自己的方法是线性复杂度,有待改进。

最佳:(基于二分查找)

class Solution {
    public int findPeakElement(int[] nums) {
        //easy solution is O(n) 
        //How to use binary search
        int l = 0, r = nums.length-1;
        while ( l < r ) {
            //System.out.println(l + " " + r);
            int m = (l+r)/2;
            int m1 = m+1;
            int m2 = m > 0 ? m-1 : m;
            //Find the target that bigger that its neighbor
            if ( nums[m] > nums[m1] && nums[m] >= nums[m2] ) {
                return m;
            } else if ( nums[m] > nums[m1] ) {
                r = m;
            } 
            // Actually can go either ways if both nums[m] lesser than both its neighbor. For the sake of simplicity, we go right so we don't need to check for other condition. 
            else  
                l = m1;
        }
        //since we check with m+1, need to return l
        return l;
    }
}