154. Find Minimum in Rotated Sorted Array II
Difficulty: Hard
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:
- This is a follow up problem to .
- Would allow duplicates affect the run-time complexity? How and why?
解法
这道题和其他三道rotated array的题都很经典，很有启发性，提醒我们要活用二分搜索，不要死记硬背套模板。
解法的核心是nums[mid] > nums[begin] or nums[mid] > nums[end]和nums[mid] < nums[end] or nums[mid] < nums[begin]和nums[mid] == nums[end] == nums[begin]三者必然只有一个成立。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class :
def findMin(self, nums: List[int]) -> int:
begin = 0
end = len(nums) - 1
while begin < end:
mid = begin + (end - begin) // 2
if nums[mid] > nums[begin] or nums[mid] > nums[end]:
if nums[mid] > nums[end]:
begin = mid + 1
else:
return nums[begin]
elif nums[mid] < nums[end] or nums[mid] < nums[begin]:
if nums[mid] < nums[begin]:
end = mid
else:
return nums[begin]
else:
end -= 1
return nums[begin]
|
相关题目
以下解法都来自https://www.happygirlzt.com/post/rotatedsortedarray/
33. Search in Rotated Sorted Array
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
|
class {
public int search(int[] nums, int target) {
int n = nums.length;
int lo = 0, hi = n - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) return mid;
if (nums[lo] <= nums[mid]) {
if (target > nums[mid] || target < nums[lo]) {
lo = mid + 1;
} else {
hi = mid - 1;
}
} else {
if (target < nums[mid] || target > nums[hi]) {
hi = mid - 1;
} else {
lo = mid + 1;
}
}
}
return -1;
}
}
|
81. Search in Rotated Sorted Array II
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
|
class {
public boolean search(int[] nums, int target) {
int n = nums.length;
int lo = 0, hi = n - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) return true;
if (nums[lo] < nums[mid] || nums[mid] > nums[hi]) {
if (target > nums[mid] || target < nums[lo]) {
lo = mid + 1;
} else {
hi = mid - 1;
}
} else if (nums[mid] < nums[hi] || nums[lo] > nums[mid]) {
if (target < nums[mid] || target > nums[hi]) {
hi = mid - 1;
} else {
lo = mid + 1;
}
} else {
hi--;
}
}
return false;
}
}
|
153. Find Minimum in Rotated Sorted Array
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 {
public int findMin(int[] nums) {
int n = nums.length;
if (nums[0] < nums[n - 1]) return nums[0];
int lo = 0, hi = n - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (mid > 0 && nums[mid] < nums[mid - 1]) {
return nums[mid];
}
if (nums[mid] > nums[mid + 1]) {
return nums[mid + 1];
}
if (nums[lo] < nums[mid]) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return nums[lo];
}
}
|
近期评论