二手商品网站的设计与建设论文,网站建设代理平台,哪个网站帮忙做户型方案,上海jsp网站建设目录1.题目2.思路3.代码实现#xff08;Java#xff09;1.题目
已知一个长度为 n 的数组#xff0c;预先按照升序排列#xff0c;经由 1 到 n 次 旋转 后#xff0c;得到输入数组。例如#xff0c;原数组 nums [0,1,4,4,5,6,7] 在变化后可能得到#xff1a;
若旋转 4…
目录1.题目2.思路3.代码实现Java1.题目
已知一个长度为 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.length 1 n 5000 -5000 nums[i] 5000 nums 原来是一个升序排序的数组并进行了 1 至 n 次旋转
进阶这道题与 寻找旋转排序数组中的最小值 类似但 nums 可能包含重复元素。允许重复会影响算法的时间复杂度吗会如何影响为什么
来源力扣LeetCode 链接https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array-ii
2.思路
1二分搜索 本题与153.寻找旋转排序数组中的最小值这题类似只不过本题中的 nums 数组可能包含重复元素。
相关题目 LeetCode_二分搜索_中等_33.搜索旋转排序数组 LeetCode_二分搜索_中等_81.搜索旋转排序数组 II LeetCode_二分搜索_中等_153.寻找旋转排序数组中的最小值
3.代码实现Java
//思路1————二分搜索
class Solution {public int findMin(int[] nums) {int left 0;int right nums.length - 1;while (left right) {int mid left (right - left) / 2;if (nums[mid] nums[right]) {//如果 nums[mid] nums[right]说明最小值在 mid 右侧left mid 1;} else if (nums[mid] nums[right]) {//如果 nums[mid] nums[right]说明最小值在 mid 左侧或者就是 mid 本身right mid;} else {//如果 nums[mid] nums[right]我们无法判断最小值在 mid 的左侧还是右侧因此将右边界缩小一位right--;}}return nums[left];}
}
