585. Maximum Number in Mountain Sequence
Maximum Number in Mountain Sequence
Given a mountain sequence of n integers which increase firstly and then decrease, find the mountain top.
Example
Example 1:
Input: nums = [1, 2, 4, 8, 6, 3]
Output: 8
Example 2:
Input: nums = [10, 9, 8, 7],
Output: 10
Notice
Arrays are strictly incremented, strictly decreasing
思路: 就是两边往中间走,最后判断start和end即可,按照九章的模板写万无一失。
class Solution:
"""
@param nums: a mountain sequence which increase firstly and then decrease
@return: then mountain top
"""
def mountainSequence(self, nums):
if nums == None or len(nums) == 0:
return -1
start, end = 0, len(nums)-1
while start + 1 < end:
mid = start + (end - start) // 2
# sqrt = mid ** 2
# sqrtPlus = (mid + 1) ** 2
if nums[mid] < nums[mid+1]:
start = mid
# elif sqrt < x:
# start = mid
else:
end = mid
if nums[start] > nums[end]:
return nums[start]
else:
return nums[end]
如果需要优化O(n)的时间复杂度,一般只能是O(logn)的二分法
binary search可以有多种写法,如果每次都写的不一样,就会造成对于结束条件,指针变化的混乱,所以我们要找到一种固定的模板,通过修改模板来解决题目。这里我选择了九章算法提供的模板。
四点要素:
start + 1 < end 这样就不用考虑两个指针的前后,最后结束时一定是相邻的
start + (end - start) / 2 虽然对python来说不重要,但是对于Java等可以防止溢出
A[mid] ==, <, > 这个会根据题目的不同来调整
A[start] A[end] ? target
请多多指教。
文章标题:585. Maximum Number in Mountain Sequence
本文作者:顺强
发布时间:2019-09-17, 23:59:00
原始链接:http://shunqiang.ml/maximum-number/版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。