LeetCode 162. Find Peak Element

162.Find Peak Element

    A peak element is an element that is greater than its neighbors.

    Given an input array nums, where nums[i] ≠ nums[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 nums[-1] = nums[n] = -∞.

    Example 1:

    Input: nums = [1,2,3,1]
    Output: 2
    Explanation: 3 is a peak element and your function should return the index number 2.
    Example 2:

    Input: nums = [1,2,1,3,5,6,4]
    Output: 1 or 5
    Explanation: Your function can return either index number 1 where the peak element is 2,
    or index number 5 where the peak element is 6.
   
     Note:
     Your solution should be in logarithmic complexity.

题目大意:在一个数组中寻找一个峰值,题目的最后一句话是一个关键,如果没有这句话,我想大多数首先想到的就是一个一个的判断,这样的话算法复杂度是O(n),实际上本题目只要求找到一个符合要求的就可以,题目中也明确的要求对数的算法复杂度,所以可以考虑利用二分查找法。

This problem is similar to Local Minimum. And according to the given condition, 
num[i] != num[i+1], there must exist a O(logN) solution. So we use binary search for this problem.
If num[i-1] < num[i] > num[i+1], then num[i] is peak
If num[i-1] < num[i] < num[i+1], then num[i+1...n-1] must contains a peak
If num[i-1] > num[i] > num[i+1], then num[0...i-1] must contains a peak
If num[i-1] > num[i] < num[i+1], then both sides have peak
(n is num.length)

首先对断点值进行判断,如果符合题意直接返回即可。不难写出基于循环的二分搜索。

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

总结:针对与以后做这种寻找满足条件的某个数的题目,都可以考虑用二分法降低时间复杂度。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏JMCui

读书笔记 之《Thinking in Java》(对象、集合、异常)

一、前言:     本来想看完书再整理下自己的笔记的,可是书才看了一半发现笔记有点多,有点乱,就先整理一份吧,顺便复习下前面的知识,之后的再补上。     真的...

3778
来自专栏余林丰

Java中net.sf.json包关于JSON与对象互转的坑

  在Web开发过程中离不开数据的交互,这就需要规定交互数据的相关格式,以便数据在客户端与服务器之间进行传递。数据的格式通常有2种:1、xml;2、JSON。通...

3855
来自专栏Jimoer

数据结构:数组、链表、栈、队列的理解

解释定义 数据结构: 数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。再简单描述一下:数据结构就是描述对象间逻辑关系的学科。 如果还是不太清楚下面会...

48510
来自专栏Java Web

Java 面试知识点解析(一)——基础知识篇

2495
来自专栏猿人谷

浅谈C/C++中的指针和数组(一)

                                                       浅谈C/C++中的指针和数组(一)       指...

2235
来自专栏苦逼的码农

谈谈fail-fast与fail-safe

fail-fast的字面意思是“快速失败”。当我们在遍历集合元素的时候,经常会使用迭代器,但在迭代器遍历元素的过程中,如果集合的结构被改变的话,就会抛出异常,防...

1324
来自专栏菜鸟计划

angularjs filter详解

过滤器(filter)正如其名,作用就是接收一个输入,通过某个规则进行处理,然后返回处理后的结果。 主要用在数据的格式化上,例如获取一个数组中的子集,对数组中的...

3798
来自专栏云霄雨霁

Java--对象的克隆

1637
来自专栏WeaponZhi

轻松初探Python(六)—函数

这是「AI 学习之路」的第 6 篇,「Python 学习」的第 6 篇 题外话 这周工作日 5 天,我并没有更新文章,但大家并不要以为小之懒惰了。正好相反,自从...

3697
来自专栏Python专栏

如何通过一些骚操作有效的控制Python类

1634

扫码关注云+社区

领取腾讯云代金券