p133 查找数组的波峰(leetcode 162)

一:解题思路

采用二分搜索的思想来做。

Time:O(log(n)),Space:O(1)

二:完整代码示例 (C++版和Java版)

C++:

class Solution {
public:
    int findPeakElement(vector<int>& nums)
    {
        if (nums.size() == 0) return -1;
        int minValue = -2147483648;
        int low = 0, high = nums.size() - 1;
        while (low < high)
        {
            int mid = low + (high-low) / 2;
            int left = mid - 1 >= 0 ? nums[mid - 1] : minValue;
            int right = mid + 1 < nums.size() ? nums[mid + 1] : minValue;
            if (nums[mid] > left && nums[mid] > right) return mid;
            else if (left > nums[mid]) high = mid - 1;
            else low = mid + 1;
        }

        return low;
    }
};

Java:

class Solution {
        public int findPeakElement(int[] nums)
        {
               if(nums==null || nums.length==0) return -1;
               int low=0,high=nums.length-1;
               while (low<high)
               {
                   int mid=low+(high-low)/2;
                   int left=mid-1>=0?nums[mid-1]:Integer.MIN_VALUE;
                   int right=mid+1<nums.length?nums[mid+1]:Integer.MIN_VALUE;
                   if(nums[mid]>left && nums[mid]>right) return mid;
                   else if(left>nums[mid]) high=mid-1;
                   else low=mid+1;
               }

               return low;
        }
    }

原文地址:https://www.cnblogs.com/repinkply/p/12708206.html

时间: 04-15

p133 查找数组的波峰(leetcode 162)的相关文章

《数据结构、算法与应用》8.(顺序查找数组中第一个出现指定元素的位置)

最近在读<数据结构.算法与应用>这本书,把书上的习题总结一下,用自己的方法来实现了这些题,可能在效率,编码等方面存在着很多的问题,也可能是错误的实现,如果大家在看这本书的时候有更优更好的方法来实现,还请大家多多留言交流多多指正,谢谢 8. 从左至右检查数组a[0:n-1]中的元素,以查找雨x相等的那些元素.如果找到一个元素与x相等,则函数返回x第一次出现所在的位置.如果在数组中没有找到这样的元素,函数则返回-1. // // main.cpp // Test_08 // // Created

动态数组,数组初始化,数组内存释放,向数组中添加一个元素,向数组中添加多个元素,数组打印,顺序查找,二分查找,查找数组并返回地址,冒泡排序,改变数组中某个元素的值,删除一个数值,删除所有,查找含有

 1定义接口: Num.h #ifndef_NUM_H_ #define_NUM_H_ #include<stdio.h> #include<stdlib.h> /************************************************************************/ /*数组的结构体类型                                                    */ /*******************

【题解】【数组】【Leetcode】Median of Two Sorted Arrays

Median of Two Sorted Arrays There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). ? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

php 查找数组中是否存在某项,并返回指定的字符串,可用于检查复选,单选等

/** * 查找数组中是否存在某项,并返回指定的字符串,可用于检查复选,单选等 * @param $id * @param $ids * @param string $returnstr * @return string */ function check_in($id,$ids,$returnstr = 'checked') { if(in_array($id,$ids)) return $returnstr; }

JS数组常用函数以及查找数组中是否有重复元素的三种常用方法

阅读目录: DS01:常用的查找数组中是否有重复元素的三种方法 DS02:常用的JS函数集锦 DS01.常用的查找数组中是否有重复元素的三种方法 1. 1 var ary = new Array("111","22","33","111"); 2 var s = ary.join(",")+","; 3 for(var i=0;i<ary.length;i++) { 4 if(s.

php折半查找(数组必须为有序)

$arr=array('1','7','9','11','20','23','33','44','50');     $len=count($arr);      $low=0;$high=$len-1;         while($low<$high)    {                  $mid=intval(($low+$high)/2);        echo $mid.'<br/>';         if($arr[$mid]>9)         {  

javascript之查找数组中最小/最大的数

实现原理:和数组的顺序查找很类似,都是逐个数据的比对. 废话不多说~ 代码如下: /* * 参数说明: * array:传入数组 ,例如:var arr = [5,7,66,78,99,103,126,203,1]; */ function findMin(array){ var _min = array[0]; //假设最小的数就是 array[0] var _indexMin = 0; //假设最小的数的下标就是0 for(var i=0;i<array.length;i++){ if(ar

挑战面试编程:查找数组中第k大的数

查找数组中第k大的数 问题: 查找出一给定数组中第k大的数.例如[3,2,7,1,8,9,6,5,4],第1大的数是9,第2大的数是8-- 思路: 1. 直接从大到小排序,排好序后,第k大的数就是arr[k-1]. 2. 只需找到第k大的数,不必把所有的数排好序.我们借助快速排序中partition过程,一般情况下,在把所有数都排好序前,就可以找到第k大的数.我们依据的逻辑是,经过一次partition后,数组被pivot分成左右两部分:S左.S右.当S左的元素个数|S左|等于k-1时,pivo

解析、查找数组中重复出现的元素(Java)

 解析.查找数组中重复出现的元素,Java实现. <数据结构与算法分析:解析.查找数组中重复出现的元素> 问题描述:一个结构化数据,假设事先按照某种顺序排好序(比如升序)的一个数组中,无规则.重复出现若干次某个相同元素,形如有序数组data: data = {  "A", "A", "B", "C", "C", "D", "D" , "D&q