LeetCode 154. Find Minimum in Rotated Sorted Array II

题目

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

Find the minimum element.

The array may contain duplicates.

Example 1:

1
2
Input: [1,3,5]
Output: 1

Example 2:

1
2
Input: [2,2,2,0,1]
Output: 0

Note:

思路

Binary-Search.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution(object):
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
p1, p2 = 0, len(nums) - 1
mid = p1
while nums[p1] >= nums[p2]:
if p2 - p1 == 1:
mid = p2
break
mid = (p1 + p2) / 2
if nums[mid] == nums[p1] and nums[mid] == nums[p2]:
return self.minInOrder(nums, p1, p2)
if nums[mid] >= nums[p1]:
p1 = mid
elif nums[mid] <= nums[p2]:
p2 = mid
return nums[mid]

def minInOrder(self, nums, index1, index2):
n1 = nums[index1]
for i in range(index1 + 1, index2):
if n1 > nums[i]:
return nums[i]
return n1