154.寻找旋转排序数组中的最小值 II (Hard)*
题目描述*
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。
注意数组中可能存在重复的元素。
示例*
输入: [1,3,5]
输出: 1
输入: [2,2,2,0,1]
输出: 0
代码*
主要区别就是有了重复元素，当边界值相同时无法判断哪一侧是旋转数组，主要有两种处理方法：
- 如果 nums[mid] == nums[right] 就把最右端丢掉，right-- 1
- 先做预处理，真正影响结果的是重复数字被分到两段中，因此只要对初始数组头尾去重。
class Solution {
public:
int findMin(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
// 预处理
while(r > 0 && nums[r] == nums[l]) {
r--;
}
while(l < r) {
int mid = l + (r - l)/2;
if(nums[mid] > nums[r]) {
l = mid + 1;
}else {
r = mid;
}
}
return nums[l];
}
};
-
貌似还是预处理快一点 ↩
最后更新: July 23, 2022