大家好呀,我是帅蛋。
今天解决寻找旋转排序数组中的最小值,这是二分查找的最后一道实战题。
真是最后一道,大家忍一下。
其实本来还有几道二分查找的题准备写的,但是看着大家对二分查找的兴趣好像不是很大,当然也可能是觉得太简单...
我也不准备写了...
话不多说,让我们快点完事。
LeetCode 153:寻找旋转排序数组中的最小值
题意
已知一个长度为 n 的数组,预先按照升序排列,经由 1 到 n 次旋转后,得到输入数组。
例如:nums = [0,1,2,4,5,6,7] 旋转 4 次可以得到 [4,5,6,7,0,1,2]。
给你一个无重复元素的数组 nums,原来是一个升序数组,并按照上述情形做了多次旋转。
请你找出并返回数组中的最小元素。
示例
输入:[4,5,6,7,0,1,2]
输出:1
解释:原数组为 [0,1,2,4,5,6,7],旋转 4 次得到输入数组。
提示
注意数组 [a[0],a[1],a[2],...,a[n-1]] 旋转一次的结果为数组 [a[n-1],a[0],a[1],...,a[n-2]]。
- 1 <= n == len(nums) <= 5000
- -5000 <= nums[i] <= 5000
- nums 中的所有整数互不相同
- nums 原先是一个升序数组,并进行了 1 ~ n 次旋转
题目解析
难度中等,值得一搞。
其实关于旋转排序数组,我们已经做过两种类型的了:
Ⅰ是数组 nums 无重复元素,Ⅱ是数组 nums 存在重复元素。
本题旋转排序数组和 Ⅰ 是一种类型,数组 nums 无重复元素。
但是本题又有不同,之前的题是给出一个 target,在 nums 中找是否存在 target,而本题是直接在旋转数组中找最小值。
题虽不同,但是做法没有大的改变,无非就是维护一个最小值的指针,每次比较就更新当前的最小值。
如果你吃透了前面两道旋转排序数组,这道题对你来说,应该是简单题。
具体步骤如下:
- 初始化一个最小值指针 nums_min。
- 找出 mid,如果 nums[mid] < nums_min,更新 nums_min。
- 如果左半区有序,维护 nums_min,范围缩小至[mid+1,high]。
- 否则就找右半区,维护 nums_min,范围缩小至[low,mid-1]。
图解
以 [4,5,6,7,0,1,2] 为例。
首先初始化 low,high 及 nums_min 指针。
low, high = 0, len(nums) - 1 nums_min = float('inf')
第 1 步,low = 0,high = 6,mid = low + (high - low) // 2 = 3:
mid = low + (high - low) // 2
此时 nums_min = inf, nums[mid] < nums_min,所以维护最小值指针 nums_min 的值。
if nums[mid] < nums_min: nums_min = nums[mid]
当前 nums[low] < nums[mid],证明左区间有序。
nums_min > nums[low],维护最小值指针 nums_min,同时 low 向右移动至 mid + 1 处。
if nums[low] < nums[mid]: if nums_min > nums[low]: nums_min = nums[low] low = mid + 1
第 2 步,low = 4,high = 6,mid = low + (high - low) // 2 = 5:
此时 nums_min = 4, nums[mid] < nums_min,所以维护最小值指针 nums_min 的值。
当前 nums[low] < nums[mid],证明左区间有序。
nums_min > nums[low],维护最小值指针 nums_min,同时 low 向右移动至 mid + 1 处。
第 3 步,low = 6,high = 6,mid = low + (high - low) // 2 = 6:
此时 nums_min = 0, nums[mid] > nums_min。
并且 nums[low] >= nums[mid],证明右区间有序,nums_min < nums[high],high 指针向右移动至 mid - 1。
此时,high < low,循环结束,返回最小值 nums_min。
本题解使用二分查找,所以时间复杂度为 O(logn)。
只是额外的维护了几个指针,所以空间复杂度为 O(1)。
代码实现
Python 代码实现
class Solution: def findMin(self, nums: List[int]) -> int: if len(nums) == 1: return nums[0] low, high = 0, len(nums) - 1 nums_min = float('inf') while low <= high: mid = low + (high - low) // 2 if nums[mid] < nums_min: nums_min = nums[mid] if nums[low] < nums[mid]: if nums_min > nums[low]: nums_min = nums[low] low = mid + 1 else: if nums_min > nums[high]: nums_min = nums[high] high = mid - 1 return nums_min
Java 代码实现
class Solution { public int findMin(int[] nums) { if(nums.length == 1){ return nums[0]; } int low = 0; int high = nums.length - 1; int nums_min = 5001; while (low <= high){ int mid = low + (high - low) / 2; if(nums[mid] < nums_min){ nums_min = nums[mid]; } if(nums[low] < nums[mid]){ if(nums_min > nums[low]){ nums_min = nums[low]; } low = mid + 1; }else{ if(nums_min > nums[high]){ nums_min = nums[high]; } high = mid - 1; } } return nums_min; } }
图解寻找旋转排序数组中的最小值到这就结束辣,这也意味着现阶段的二分查找到这就结束了。
如果是认真跟下来的小宝贝肯定是收获满满,这点我还是很自信的。
还是那句话,总体来说呢,二分查找就是个事儿精,细节控,在用二分的时候一定要打起十二分精神。
下面我们来开始新的专题,如果期待的话,记得给我三连:点赞 + 在看 + 转发。
让我看到你!
我是帅蛋,我们下次见