1. 解题思路
拿到这个题的第一反应就是使用min函数不就可以解决(暴力解法)?!于是输入如下代码。
2. 核心代码
# -*- coding:utf-8 -*- class Solution: def minNumberInRotateArray(self, rotateArray): # write code here if len(rotateArray) == 0: #根据题目提示先注意数组大小为0的情况 return 0 else: return min(rotateArray) #然后直接用min函数找出最小数字
果真很暴力🤣,而且时间还行!
不过本题不是考这个知识点,所以该解法大家就了解一下。
3. 复杂度分析
- 时间复杂度: (n 为数组的长度)
- 空间复杂度: (没有额外空间的使用)
-------------------------------------------------我是解法二的分割线---------------------------------------------
4. 解法二
4.1 思路:二分查找
此题其实是要考察二分查找(指每次都跟中间元素值比较大小,然后将待查找区间缩小为之前的一半,直到找到要求的元素值或区间为0)这个知识点。回到本题,我们还是以示例1进行思路的图解。
- 首先初始化分界的左右下标left,right,然后寻找初始中间点下标middle:
- 接着判断最小数字在哪个区间内,进行二分查找:
- 第一种情况,当中间点的值 大于右边界值时:可知最小数字在右区间,此时忽略左区间,右边界下标不变,更新左边界下标。因为中间点是大于最右值的,此时它肯定不是最小值,那么二分后的左边界只会是从 middle + 1 的下标开始,右边界依然是right下标,所以整个区间范围即[middle + 1 , right];
- 第二种情况,当中间点的值 小于右边界值时:同理可知最小数字在左区间,此时忽略右区间,左边界下标不变,更新右边界下标,即right = middle;
由于示例1此时只剩一个数字,且left下标 == right下标,所以跳出刚刚的循环,直接返回该数字即可。
- 第三种情况,当中间点的值 等于右边界值时:这种情况发生在一个包含重复数字的旋转数组中,看下面这个示例。
此时middle对应值和right 对应值是相等的,那么只有把右边界缩小 1位才能继续进行查找。具体过程如下:
- 第一种情况,当中间点的值 大于右边界值时:可知最小数字在右区间,此时忽略左区间,右边界下标不变,更新左边界下标。因为中间点是大于最右值的,此时它肯定不是最小值,那么二分后的左边界只会是从 middle + 1 的下标开始,右边界依然是right下标,所以整个区间范围即[middle + 1 , right];
4.2 核心代码
# -*- coding:utf-8 -*- class Solution: def minNumberInRotateArray(self, rotateArray): # write code here if len(rotateArray) == 0: return 0 #首先定义最左和最右两个下标变量 left = 0 right = len(rotateArray) - 1 #下面开始二分查找 while left < right: #首先找到初始中间点,这里用位运算处理更快 middle = left + ((right - left)>> 1) #下面开始根据最左和最右值与中间值得大小,找最小数字 if rotateArray[middle] > rotateArray[right]: #当中间值大于最右值时,根据旋转数组定义,此时可知最小值在右区间,所以可以忽略左区间 #由于中间点是大于最右值的,所以中间点一定不是最小值!那么最小值就在中间点右边,所以这里middle+1,更新最左边界下标 left = middle + 1 elif rotateArray[middle] < rotateArray[right]: #当中间值小于最右值,忽略右区间 right = middle #此时只需要更新最右边界下标的位置 else: right = right - 1 #当中间值等于最右值时,此情况存在于数组中有重复数字的时候:直接右边界下标减一来更新右边界 #当左边界下标 == 右边界下标时,数组只有一个数字就是最小数字,退出循环,直接返回左边界对应值即可 return rotateArray[left]
4.3 复杂度分析
- 时间复杂度:
(n 为数组的长度, 大部分情况下都会忽略一半区间;最坏情况下,当数组中元素完全相同时,while会循环n次,这种情况的时间复杂度退化为) - 空间复杂度: (left, middle, right都使用的是常数大小的空间)