mirror of
https://github.com/ShusenTang/LeetCode.git
synced 2024-09-02 14:20:01 +00:00
41 lines
2.1 KiB
Markdown
41 lines
2.1 KiB
Markdown
# [153. Find Minimum in Rotated Sorted Array](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/)
|
||
# 思路
|
||
要求一个经过循环移位后的排序数组(无重复元素)中的最小值.
|
||
其实这题是[33. Search in Rotated Sorted Array](https://github.com/ShusenTang/LeetCode/blob/master/solutions/33.%20Search%20in%20Rotated%20Sorted%20Array.md)
|
||
的前半部分, 所以搞懂33题了这题肯定完全没问题.
|
||
|
||
由于数组(移位前)是有序的所以肯定是二分, 设最小值在i处, 则数组A = nums[0,...,i-1]和B = nums[i,...,n-1]是分别递增的, 而且B的所有元素都小于A任意元素.
|
||
二分while循环中mid需要分三种情况:
|
||
1. 当`nums[low] > nums[mid]`时, 说明mid在B部分, 则i在区间[low, mid];
|
||
2. 否则即mid在A部分(B存不存在未知), 此时当`nums[low] > nums[high]`时, 说明B部分存在, 则i在区间[mid+1, high];
|
||
3. 否则, 即mid在A部分且B不存在, 即low到high是严格递增的, 最小值即nums[low], 直接返回即可.
|
||
|
||
或者考虑`nums[high]`和`nums[mid]`的大小关系（考虑`nums[low]`和`nums[mid]`关系不是一个好选择, 见[33题解](https://github.com/ShusenTang/LeetCode/blob/master/solutions/33.%20Search%20in%20Rotated%20Sorted%20Array.md)）也可以：
|
||
* 若`nums[mid] < nums[high]`，此时最小值只能是位于[low, mid]。
|
||
* 否则若`nums[mid] > nums[high]`，此时最小值只能是位于[mid+1, low]。
|
||
* 假设`nums[mid] == nums[high]`，此时low = mid = high，最小值就是nums[mid]。
|
||
|
||
> 注意边界情况.
|
||
|
||
# C++
|
||
``` C++
|
||
class Solution {
|
||
public:
|
||
int findMin(vector<int>& nums) {
|
||
int low = 0, high = nums.size() - 1, mid;
|
||
|
||
while(low <= high){
|
||
mid = low + (high - low) / 2;
|
||
if(nums[low] > nums[mid]) high = mid;
|
||
else if(nums[low] > nums[high]) low = mid + 1;
|
||
else return nums[low];
|
||
// 或者:
|
||
// if(nums[mid] > nums[high]) low = 1 + mid;
|
||
// else if(nums[mid] < nums[high]) high = mid;
|
||
// else return nums[low];
|
||
}
|
||
return nums[low]; // 这一步应该是不会执行的
|
||
}
|
||
};
|
||
```
|