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

寻找旋转排序数组中的最小值题目链接https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/?envTypestudy-plan-v2envIdtop-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。总结本题主要需要结合“一个不包含重复元素的升序数组在经过旋转之后所有数据值的大小的分布特点”来进行剪枝从而实现O(n)的时间复杂度解题。