LeetCode | 每日一题 2021.10.14 | 山峰数组的顶部

10/14 14:19
阅读数 0
"""
https://leetcode-cn.com/problems/B1IidL/
思路:
    方法1:循环查找最大值
        因为题目给定的假设就是[由整数组成的山峰数组],
        实际上峰顶就是求整个数列的最大值;
        note:这个方法的复杂度是O(n)
    方法2:二分查找
        1. 在[0-n]的闭区间[left,right]获取中间值下标
            mid=[left+(right-left)]//2
        2.条件判断
        2.1 如果mid比两边值都大,就是目标峰顶值,返回mid
            arr[mid]>arr[mid-1] and arr[mid]>arr[mid+1]
        2.2 如果mid比mid-1小,但比mid+1大,
            说明峰值在[left,mid]区间,right左移=mid
        2.3 如果mid比mid+1小,但比mid-1大,
            说明峰值在[mid,right]区间,left右移=mid
"""
class Solution:
    #方法1:循环查找最大值
    def peakIndexInMountainArray_Max(self, arr):
        max=0                               #初始化一个值
        for i in range(0,len(arr)):
            if arr[i]>arr[max]:                 #两数相比
                max=i                      #获取较大值下标
        return max
    # 方法2:二分查找
    def peakIndexInMountainArray_BinarySearch(self, arr):
        left=0
        right=len(arr)-1
        while left<right:
            # 计算中间值下标,//表示整除
            mid=left+(right-left)//2
            # 如果mid比两边值都大,就是目标峰顶值,返回mid
            if arr[mid]>arr[mid-1] and arr[mid]>arr[mid+1]:
                return mid
            # 如果mid比mid-1小,但比mid+1大
            #不需要进行arr(mid)>arr(mid+1)判读,因为第一步已经处理
            elif arr[mid]<arr[mid-1]:
                right=mid
            # 如果mid比mid+1小,但比mid-1大
            #不需要进行arr(mid)>arr(mid-1)判读,因为第一步已经处理
            elif arr[mid]<arr[mid+1]:
                left=mid
        #返回一个负值,防止出错情况
        return -1

arr=[1,3,5,4,2]
ans1=Solution().peakIndexInMountainArray_Max(arr)
ans2=Solution().peakIndexInMountainArray_BinarySearch(arr)
print(ans1,ans2)

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部