LeetCode-Python-162. ピークを探す

2356 ワード

ピーク要素とは、その値が左右の隣接値より大きい要素を指す.
入力配列numsが与えられ、nums[i] ≠ nums[i+1]は、ピーク要素を見つけ、そのインデックスを返す.
配列には複数のピークが含まれる場合があります.この場合、いずれかのピークの位置を返します.nums[-1] = nums[n] = -∞と仮定できます.
例1:
  : nums = [1,2,3,1]
  : 2
  : 3      ,            2。

例2:
  : nums = [1,2,1,3,5,6,4]
  : 1   5 
  :            1,       2;
            5,        6。

説明:
あなたの解法はO(logn)時間の複雑さのはずです.
第一の考え方:
与えられた条件nums[i] ≠ nums[i+1],は、最大値の下付きを直接探せばよい.
class Solution(object):
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return nums.index(max(nums))
        

2つ目の考え方: :nums[-1] = nums[n] = -∞, i=0 nums[i], nums[i] > nums[i+1] , [2,3,2,9,8], i 1, 3, 。 nums[i] > nums[i+1] , ( ), nums[i] > nums[i+1] ,num[i] , 。
class Solution(object):
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) <= 1:
            return 0
        for index, item in enumerate(nums):
            if index < len(nums) - 1 and item > nums[index + 1]:
                return index
        return len(nums) - 1

3つ目の考え方:
第2の考え方に基づいて、二分検索の思想を運用し、
midがピークかどうかを判断するたびに、そうでなければ大きな側に検索を続けます.
class Solution(object):
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
          
        if len(nums) <= 1:
            return 0
        lo, hi = 0, len(nums) - 1
        while(lo < hi):
            # print lo,hi
            mid = lo + (hi - lo) / 2
            if nums[mid - 1] < nums[mid] and nums[mid] > nums[mid + 1]:
                return mid
            elif nums[mid] < nums[mid + 1]:
                lo = mid + 1
            else:
                hi = mid - 1
                
        return lo