(Leetcode 2021 刷题计划) 154. 寻找旋转排序数组中的最小值 II
原创(Leetcode 2021 刷题计划) 154. 寻找旋转排序数组中的最小值 II
原创
windism
修改于 2021-04-12 10:23:53
修改于 2021-04-12 10:23:53
每日一题时间:
2020-04-09题目链接: 154. 寻找旋转排序数组中的最小值 II 官方题解链接: 寻找旋转排序数组中的最小值 II
题目
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：
- 若旋转
4次，则可以得到[4,5,6,7,0,1,4] - 若旋转
7次，则可以得到[0,1,4,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个可能存在 重复 元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
示例 1：
输入：nums = [1,3,5]
输出：1
示例 2：
输入：nums = [2,2,2,0,1]
输出：0提示：
n == nums.length1 <= n <= 5000-5000 <= nums[i] <= 5000nums原来是一个升序排序的数组，并进行了1至n次旋转
进阶：
- 这道题是 寻找旋转排序数组中的最小值 的延伸题目。
- 允许重复会影响算法的时间复杂度吗？会如何影响，为什么？
解题方法
暴力解题
class Solution {
public:
int findMin(vector<int>& nums) {
int res = nums[0];
for (auto &n: nums) {
res = min(n, res);
}
return res;
}
};- 复杂度分析
- 时间复杂度:
O(N) - 空间复杂度:
O(1)
- 时间复杂度:
二分查找
解题思路: 相较于 153. 寻找旋转排序数组中的最小值 增加可能存在相等数值的可能，针对这样的情况，在于如果二分查找中间的元素与右边元素对比相等时，无法判断应当在左右哪个空间，因此仅能递减右边界进行获取。
class Solution {
public:
int findMin(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < nums[right]) {
right = mid;
} else if (nums[mid] > nums[right]) {
left = mid + 1;
} else {
--right;
}
}
return nums[left];
}
};- 复杂度分析
- 时间复杂度:
O(N)(极端情况，完全相等) - 空间复杂度:
O(1)
- 时间复杂度:
参考资料
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录