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.
Note:
Your solution should be in logarithmic complexity.
public int findPeakElement(int[] num) { int n = num.length; int low = 0, high = n-1; while(low <= high) { int mid = (low + high) / 2; if((mid == 0 || num[mid] > num[mid-1]) && (mid == n-1 || num[mid] > num[mid+1])) { return mid; } else if(mid > 0 && num[mid] <= num[mid-1]) { high = mid-1; } else { low = mid+1; } } return -1; }
References:
http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf
http://www.youtube.com/watch?v=HtSuA80QTyo
相关推荐
javascript js_leetcode题解之162-find-peak-element.js
python python_leetcode题解之162_Find_Peak_Element.py
java java_leetcode题解之Find Peak Element
leetcode 分类 :person_running::person_running::person_running: 算法 :person_running::person_running::person_running: 实践&理论 :books: :ear: :television: Binary Search(二分查找) easy 69: 278: 35: ...
- **查找峰值元素(Find Peak Element)**: 在一个无序数组中找到任意一个局部最大值。 - **在旋转排序数组中搜索/Search in Rotated Sorted Array**: 在一个被旋转过的排序数组中搜索给定数字。 - **在旋转排序数组中...
next-greater-element-ii serialize-and-deserialize-binary-tree subarray-sum-equals-k binary-tree-preorder-traversal n-queens-ii populating-next-right-pointers-in-each-node sum-root-to-leaf-numbers best...
- Find Peak Element(寻找峰值元素) - Search in Rotated Sorted Array(在旋转排序数组中搜索) - Search in Rotated Sorted Array II(在旋转排序数组中搜索II) - Find Minimum in Rotated Sorted Array...
leetcode 刷题笔记 记录一些刷题细节,很惭愧只做了一点微小的工作 4.13 162题. Find Peak Element.Binary search,需要比较nums[mid]和nums[mid+1]. 4.12 212题. Word Search II. 用trie tree存word list,然后dfs. ...
element(162).swift Leetcode\find重复的数字(287).swift Leetcode\friend circles(547).swift Leetcode\gas station(134)。 swift Leetcode\group anagrams(49).swift Leetcode\group 给定他们所属的组大小的人...
lru cache leetcode Coding-Interview ...Peak Element First Bad Version Valid Perfect Square 二叉树查找/BST查找 Closest Binary Search Tree Value 二叉树查找/二叉树第K个 Kth Smallest Element In A
1. Introduction 2. Array i. Remove Element ii. Remove Duplicates from Sorted Array iii....iv....v....vi....vii. Find Minimum in Rotated Sorted Array viii....ix....x....xi....xii....xiii....xiv. Find Peak Element
从标题和描述中可以看到,本文主要关注于LeetCode原题的总结,涵盖了162个题目,包括Find Peak Element、Isomorphic Strings、Group Shifted Strings等,这些题目都是Google Onsite面经中的常见题目。 下面将对这些...
- **寻找峰值元素(Find Peak Element)**: 给定一个未排序的数组,找到一个“峰值”元素,即其值大于相邻元素。 ##### 位操作(Bit Manipulation) - **缺失数字(Missing Number)**: 给定一个包含[0, n]范围内所有...
- Find Peak Element:在一个整数数组中找到一个峰值元素。 - Median of Two Sorted Arrays:两个排序数组的中位数。 - Sqrt(x):计算并返回x的平方根。 - Wood Cut:木材切割问题,给定木材长度,求可以切出的最大...