[Swift]LeetCode162. 寻找峰值 | Find Peak Element

发布时间：2020-12-14 05:09:08 所属栏目：百科来源：网络整理

导读：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 o

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 = 
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.[1,2,3,1]

Example 2:

Input: nums = 1,1,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.

峰值元素是指其值大于左右相邻值的元素。

给定一个输入数组?nums，其中?nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。

数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

你可以假设?nums[-1] = nums[n] = -∞。

示例 1:

输入: nums = 
输出: 2
解释: 3 是峰值元素，你的函数应该返回其索引 2。[1,1]

示例?2:

输入: nums = 1,4]
输出: 1 或 5 
解释: 你的函数可以返回索引 1，其峰值元素为 2；
?    或者返回索引 5， 其峰值元素为 6。
[

说明:

你的解法应该是?O(logN)?时间复杂度的。

32ms

 1 class Solution {
 2     func findPeakElement(_ nums: [Int]) -> Int {
 3         var low = 0
 4         var high = nums.count - 1
 5         
 6         while low != high {
 7             let mid = (low + high)/2
 8             
 9             if !nums.indices.contains(mid - 1) {
10                 if nums[mid + 1] < nums[mid] { return mid }
11                 low = mid + 1
12                 continue
13             }
14             
15             if nums[mid - 1] < nums[mid] && nums[mid + 1] < nums[mid] {
16                 return mid
17             } 
18             
19             if nums[mid - 1] < nums[mid] && nums[mid + 1] > nums[mid] {
20                 low = mid + 1
21                 continue
22             }
23             
24             high = mid - 1
25         }
26         
27         return high
28     }
29 }

36ms

 1 class Solution {
 2     func findPeakElement(_ nums: [Int]) -> Int {
 3             guard nums.count > 1 else{
 4                 return 0
 5             }
 6             var left = 0
 7             var right = nums.count  - 1
 8             while left < right{
 9                 let middle = (left + right) / 2
10                 if nums[middle] > nums[middle + 1] {
11                     right = middle 
12                 }else{
13                     left = middle + 1
14                 }
15             }
16         
17         return left
18         
19     }
20     
21 }

40ms

 1 class Solution {
 2     func findPeakElement(_ nums: [Int]) -> Int {
 3         if nums.count >= 3 {
 4             for i in Array(1..<nums.count - 1) {
 5                 let left = nums[i - 1]
 6                 let value = nums[i]
 7                 let right = nums[i + 1]
 8 
 9                 if value > left && value > right {
10                     return i
11                 }
12             }
13         }
14         
15         let lower = 0
16         let upper = nums.count - 1
17         
18         return nums[lower] >= nums[upper] ? lower : upper
19     }
20 }

44ms

 1 class Solution {
 2     func findPeakElement(_ nums: [Int]) -> Int {
 3         var low = 0
 4         var high = nums.count - 1
 5         
 6         while low != high {
 7             let mid = (low + high)/2
 8             
 9             if !nums.indices.contains(mid - 1) || nums[mid - 1] < nums[mid] {
10                 if nums[mid + 1] < nums[mid] { return mid }
11                 low = mid + 1
12                 continue
13             }
14             
15             high = mid - 1
16         }
17         
18         return high
19     }
20 }

52ms

 1 class Solution {
 2     func findPeakElement(_ nums: [Int]) -> Int {
 3 var left = 0
 4     var right = nums.count - 1
 5     var mid = 0
 6     
 7     while left < right {
 8         mid = (right - left) / 2 + left
 9         
10         if nums[mid] > nums[mid + 1] {
11             right = mid
12         } else {
13             left = mid + 1
14         }
15     }
16     return left
17     }
18 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!