LeetCode-Python-162. ピークを探す
ピーク要素とは、その値が左右の隣接値より大きい要素を指す.
入力配列
配列には複数のピークが含まれる場合があります.この場合、いずれかのピークの位置を返します.
例1:
例2:
説明:
あなたの解法はO(logn)時間の複雑さのはずです.
第一の考え方:
与えられた条件
2つ目の考え方:
3つ目の考え方:
第2の考え方に基づいて、二分検索の思想を運用し、
midがピークかどうかを判断するたびに、そうでなければ大きな側に検索を続けます.
入力配列
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