leetcode【162】Find

image description

leetcode【162】Find

写在最前面:

这可能是我做过的最简单的中等难度的题了 leetcode【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 =

Input: nums = 
[1,2,3,1]

Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

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. 没啥好说的

class Solution(object):
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        if len(nums) == 1:
            return 0
        for i in range(1,len(nums)-1):
            if nums[i-1] < nums[i] & nums[i] > nums[i+1]:
                return i
        for i in range(0, len(nums) - 1):
            if nums[i] > nums[i+1]:
                return i
        for i in range(0, len(nums)):
            if nums[len(nums)-1] > nums[len(nums)-2]:
                return len(nums)-1

真的很简单,难道有更快的?

我看到有的人用二分,水平可以,就是没必要,找到第一个就可以了好么,要那么复杂干嘛

但是,二分法是很值得讲一讲的

其实我们只需要找到连续的三个数,中间那个比两边大即可。用二分的话,就是从中间开始找第一个峰值。

我们找到一个数,然后向左向右缩小范围,直到left和right两个指针重合。

如果大家理解不了,可以自己手动纸上画一画

二分真的是一种很棒的思想

class Solution(object):
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        left  = 0 
        right = len(nums)-1
        while left < right:
            mid = (left + right) // 2
            if nums[mid]  > nums[mid+1]:
                right = mid 
            elif  nums[mid] < nums[mid + 1]:
                left = mid + 1
        return right
    ArithmeticJia         0         1309         Leetcode         12    

David Ramon

ArithmeticJia

www.guanacossj.com

Life is Short,You need Python

Related Posts

You may like these post too

image description

leetcode【400】Nth Digit

##写在最前面: 为什么我觉得这道简单的题好难啊...感觉自己是个数学渣渣 纯原创,不会有人和我一样奇葩的思路的... ##leetcode【400】Nth Digit Find the nth digit of the infinite integer sequence 1,

image description

leetcode【763】Partition Labels(使用贪心算法划分字母区间)

##写在最前面 刷leetcode就像头脑风暴,也是各种算法的灵活运用。 其实介绍一点语法,介绍一个模块的调用相比刷leetcode,做算法轻松太多,用来刷积分,刷文章数再简单不过. 可总要做一点有挑战的事才有意义吧. by the way,我破邮的教室都装上空调了,果然评了双一

Comments on this post

0 comments

Leave a comment

it’s easy to post a comment

image description
image description
image description
image description
image description
image description
image description
image description
image description

Copyright © 2019.Company name All rights reserved.苏ICP备19007197号