当前位置：首页 > news >正文

067寻找旋转排序数组中的最小值

news 2026/5/31 14:07:48

寻找旋转排序数组中的最小值

题目链接：https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/?envType=study-plan-v2&envId=top-100-liked

我的解答：

public int findMin(int[] nums) { return check(nums, 0, nums.length - 1); } public int check(int[] nums, int l, int r){ while(l <= r){ int mid = l + ((r - l) >> 1); if(mid + 1 < nums.length && nums[mid] > nums[mid + 1]){ return nums[mid + 1]; } else if(mid - 1 >= 0 && nums[mid] < nums[mid - 1]){ return nums[mid]; } else{ return Math.min(check(nums, l, mid - 1), check(nums, mid + 1, r)); } } return r >= 0 ? nums[r] : nums[l]; }

分析：代码的时间复杂度为O(n)，空间复杂度为O(logn)。自己未能想出时间复杂度为O(logn)的解法。解题思路：二分查找+递归，虽然是二分查找，但是没有根据旋转排序数组的特点进行剪枝，每一个元素都被访问了一遍，让时间复杂度到达了O(n)，因此不推荐此方法。

看了官方题解后的解答：

//方法：二分查找 //时间复杂度：O(logn) //空间复杂度：O(1) public int findMin(int[] nums) { int l = 0, r = nums.length - 1; while(l < r){ int mid = l + ((r - l) >> 1); if(nums[mid] < nums[r]){ r = mid; } else{ l = mid + 1; } } return nums[r]; }

分析：

1、解题思路，利用旋转排序数组的特点进行剪枝。

2、旋转排序数组的特点：一个不包含重复元素的升序数组在经过旋转之后，可以得到下面可视化的折线图：

3、[l,r]维护最小值可能出现的范围，初始时l = 0, r = nums.length-1，每次将中间位置的元素与右边界的元素作比较，若nums[mid] < nums[r]，说明nums[mid]是最小值或最小值右侧的元素，因此我们可以忽略二分查找区间的右半部分，让r = mid；若nums[mid] > nums[r]，说明nums[mid]是最小值左侧的元素，因此我们可以忽略二分查找区间的左半部分，让l = mid +1。