leetcode-153-Find-Minimum-in-Rotated-Sorted-Array

描述


Suppose a sorted array 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.

You may assume no duplicate exists in the array.

分析


寻找旋转排序数组中的最小值,最差的情况是 $O(n)$,一次遍历就行了。用二分法是更好的做法,判断的条件是左边的值大于右边的值,这时要找的这个值一定在左右两个数的中间,这时的时间复杂度是 $O(lg(n))$

解决方案1(Python)


蛮力法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""

nums_len = len(nums)
if nums_len == 1:
return nums[0]

for i in range(nums_len-1):
if(nums[i+1]<nums[i]):
return nums[i+1]

return nums[0]

二分法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""

nums_len = len(nums)
if nums_len == 1:
return nums[0]

left = 0
right = nums_len - 1

while(nums[left] > nums[right]):
mid = (left + right) / 2
if nums[mid] > nums[right]:
left = mid + 1
else :
right = mid
return nums[left]

解决方案2(C++)


蛮力法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int findMin(vector<int>& nums) {
int len = nums.size();
if(len == 1) {
return nums[0];
}

for(int i = 1; i < len; i++) {
if(nums[i] < nums[i-1]) {
return nums[i];
}
}
return nums[0];
}
};

二分法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int findMin(vector<int>& nums) {
int len = nums.size();
if(len == 1) {
return nums[0];
}

int left = 0, right = len-1;

while(nums[left] > nums[right]) {
int mid = (left + right) / 2;
if(nums[mid] > nums[right]) {
left = mid + 1;
}else {
right = mid;
}
}
return nums[left];
}
};

解决方案3(Golang)


二分法。

1
2
3
4
5
6
7
8
9
10
11
12
func findMin(nums []int) int {
low, high := 0, len(nums) - 1
for low < high {
mid := low + (high-low) / 2
if nums[mid] < nums[high] {
high = mid
} else {
low = mid + 1
}
}
return nums[low]
}

相关问题


题目来源