-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy path153寻找旋转排序数组中的最小值.py
42 lines (37 loc) · 1.24 KB
/
153寻找旋转排序数组中的最小值.py
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
'''
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。
你可以假设数组中不存在重复元素。
示例 1:
输入: [3,4,5,1,2]
输出: 1
示例 2:
输入: [4,5,6,7,0,1,2]
输出: 0
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
'''
class Solution:#44ms,13.7MB
def findMin(self, nums):
left, right = 0, len(nums) - 1
while (left < right):
mid = left + (right - left) // 2
if nums[mid] > nums[mid + 1]:
return nums[mid + 1]
if (nums[mid] < nums[right]):
right = mid
else:
left = mid + 1
return nums[0]
class Solution2:#44ms,13.6MB
def findMin(self, nums):
if len(nums) == 0:
return 0
if len(nums) == 1:
return nums[0]
for i in range(len(nums) - 1):
if nums[i] > nums[i + 1]:
return nums[i + 1]
return nums[0]