- 浏览: 173163 次
- 性别:
- 来自: 济南
文章分类
最新评论
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.
按照题目的要求,从一个数组中找到一个数比它的邻居都大。数组有几个特征,没相邻的两个元素不同,并且题目中假设num[-1] = num[n] = -∞。这样我们可以确定的是除非数组为空,否则数组中肯定会存在一个peak element。我们可以用二分法,从中间元素开始比较,如果nums[m] > nums[m + 1]说明m + 1左边肯定存在peak元素,我们就从左部分找;如果nums[m] < nums[m + 1]说明m右边肯定存在peak元素,我们从右半部分查找。这样时间复杂度为O(nlogn)。代码如下:
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.
按照题目的要求,从一个数组中找到一个数比它的邻居都大。数组有几个特征,没相邻的两个元素不同,并且题目中假设num[-1] = num[n] = -∞。这样我们可以确定的是除非数组为空,否则数组中肯定会存在一个peak element。我们可以用二分法,从中间元素开始比较,如果nums[m] > nums[m + 1]说明m + 1左边肯定存在peak元素,我们就从左部分找;如果nums[m] < nums[m + 1]说明m右边肯定存在peak元素,我们从右半部分查找。这样时间复杂度为O(nlogn)。代码如下:
public class Solution { public int findPeakElement(int[] nums) { if(nums == null || nums.length == 0) return -1; if(nums.length == 1) return 0; int l = 0; int r = nums.length - 1; while(l < r) { int m = l + (r - l) / 2; if(nums[m] > nums[m + 1]) { r = m; } else { l = m + 1; } } return l; } } :twisted:
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 224Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 222You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 339Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 330Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 448Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 508Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 427Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 617Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 425The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 383Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 514Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 528Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 366All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 858Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 879Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 552Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 598Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 761Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 731You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 626For a undirected graph with tre ...
相关推荐
(3)162. Find Peak Element (2)205. Isomorphic Strings (3)249. Group Shifted Strin
经典的寻峰算法,对初学者有帮助,maylab编写的,有一些注释
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
寻找峰值算法应用广泛,matlab的峰值计算函数findpeaks()可设置峰值间隔、峰值门限、峰值宽度等等参数,非常好用。压缩包中包含matlab中的findpeaks()函数的所有输入参数说明、.m源码、详细导出步骤以及导出的c++...
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
使用Array.prototype.find()使用更复杂的条件查找元素 介绍 作为开发人员,我们需要定期做的一件事情是将对象放置在数组中。 能够存储数据固然很好,但是除非我们能够再次将其取回,否则它是毫无用处的。 在...
34.Find_First_and_Last_Position_of_Element_in_Sorted_Array在排序数组中
peak element 34: find first and last position of element in sorted array 300: longest increasing subsequence hard 154: find minimum in rotated sorted array ii 315: count of smaller numbers after self ...
个人资源中DOA算法缺失的findpeak函数。下载后放到同级目录即可使用。此函数就是为了找到数组最大值对应的方位角。
find_max_element_in_unsorted_LL_iterative问题: class ListNode { constructor(value = 0, next = null) { this.value = value this.next = next }} function findMax(head) { // Write your code here....
element(162).swift Leetcode\find重复的数字(287).swift Leetcode\friend circles(547).swift Leetcode\gas station(134)。 swift Leetcode\group anagrams(49).swift Leetcode\group 给定他们所属的组大小的人...
driver.find_element_by_id("kw").send_keys(Keys.CONTROL, 'a') (12)通过模拟Control + x 键剪切输入框内容,往输入框重新输入搜索关键字“itcast”: >>> driver.find_element_by_id("kw").send_keys(Keys....
3. find an element by book name (linear search) 4. find an element by book name (binary search) 5. delete an element at position 6. delete an element by book name 7. sort the list (using ...
driver.find_element_by_id() # id定位 driver.find_element_by_name() # name定位 driver.find_element_by_class_name() # class名称定位 driver.find_element_by_tag_name() # 标签定位 driver.find_element_...
find_element_by_( ),是用来定位单个元素的,find_elements_by_( ),是用来定位多个元素的。 通过 id 定位 通过 name 定位 通过 class 定位 通过 tag 定位 通过 link 定位 通过 partial link 定位 通过 ...
Find Peak Element.Binary search,需要比较nums[mid]和nums[mid+1]. 4.12 212题. Word Search II. 用trie tree存word list,然后dfs. 4.11 788题. Rotated Digits.转换成字符串,时间复杂度O(nlogn).还可以用dp,dp...
VB 查找函数Find VB 查找函数Find VB 查找函数Find
gethibernatetemplate的find方法,find(String queryString);find(String queryString , Object value);find(String queryString, Object[] values);findByExample(Object exampleEntity);findByExample(Object ...
14年6月份在《Science》期刊上发表的的一篇论文,论文中提出了一种非常巧妙的聚类算法
findpeaks吗? 包含在Scipy中 ? ✘ 包含在Scipy 0.11+中 最小距离 ✘ 包含在Scipy 1.1+中 振幅临界点距离突出性宽度 :check_mark: 单一档案来源取决于脾气暴躁 最小距离最小高度相对阈值 :check_mark: PyPI软件包...