前言
今天继续算法题:旋转数组的最小数字
题目:旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转,该数组的最小值为1。
示例 1:
输入:[3,4,5,1,2] 输出:1 示例 2:
输入:[2,2,2,0,1] 输出:0
解法一
首先找到题目的提干:
递增排序数组(可以重复),旋转,最小元素
也就是一个递增数组,将一部分移动到数组尾部,比如:
- [1,2,3,4,5]
- //旋转之后
- [3,4,5,1,2]
找到其中的最小数字。
那么我们很容易想到的第一中解法就是遍历数组,然后找到某一个数字比它前面一个数字小的时候,那么这个数字就是我们要找的最小数字。
因为正常来说都是后面数字大于前数字,所以出现小于前数字,那么就是这个旋转数组的分界点,也就是最小数字了。
- class Solution {
- public int minArray(int[] numbers) {
- for(int i=0;i<numbers.length-1;i++){
- if(numbers[i]>numbers[i+1]){
- return numbers[i+1];
- }
- }
- return numbers[0];
- }
- }
方法消耗情况
以后不写这个了。由于每次测试用例不同,造成的结果也相差太大,没有参考性。
时间复杂度
遍历一次数组,所以时间复杂度为O(n)
空间复杂度
没有用到另外的空间,所以空间复杂度为O(1)
解法二
二分法。
有的人可能会疑惑,二分法不是用来查找顺序数组的吗,这个旋转之后也算吗?
我们回顾下二分法的关键点就是:
取任意一个关键数字,都能通过判断 来确定在我们要的值在哪个区间(关键数字的前后)。
那么在我们的旋转数组中,能做到这一点吗?
比如我们取中间值a和最后值b,如果a大于b,就说明这个分界值在这a和b之间,a之前的数据是正确排序的。
如果a小于b,说明分界值在a之前,a到b之间的数据是正确排序的。
比如刚才的[3,4,5,1,2],中间值5大于最后的值2,说明分界值在5和2之间,也就是1了。
- class Solution {
- public int minArray(int[] numbers) {
- int left=0;
- int right=numbers.length-1;
- //二分法查找条件
- while(left<right){
- //找到中间点
- int mid=left+(right-left)/2;
- if(numbers[mid]<numbers[right]){
- right=mid;
- }else if(numbers[mid]>numbers[right]){
- left=mid+1;
- }else{
- right--;
- }
- }
- return numbers[left];
- }
- }
其中right=mid,left=mid+1的原因是因为,当numbers[mid]
而numbers[mid]>numbers[right]的情况下,mid不可能为最小,所以设置为mid+1。
时间复杂度
二分法最坏情况:
n/(2的x次方)=1,x=long2n。所以时间复杂度为O(longn)
还有一种情况是所有元素全部相同,这种情况下每次都执行right-1,所以时间复杂度为O(n)
空间复杂度
没有用到另外的空间,所以空间复杂度为O(1)
参考
https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/submissions/
本文转载自微信公众号「 码上积木」,可以通过以下二维码关注。转载本文请联系 码上积木公众号。
自2011年以来SAP一直在其HANA基础内存数据平台上进行构建,已成功实施了2700多个...
冠状病毒疫情如今正在全球各地持续蔓延,为有效应对病毒,需要共享一些公共卫生...
云 服务器托管 租用价格?不少 云服务器 厂商既提供自己的服务器品牌供用户选择...
Qcon2021北京站《低代码实践与应用》分论坛由阿里云智能钉钉事业部资深技术专家...
GitHub是一个平台,来自世界各地的程序员可以共享他们的代码。这是一个协作,学...
车联网是汽车、电子、信息通信、交通运输和交通管理等行业深度融合的新型产业形...
域名 怎么做实名认证?域名的实名认证其实很简单,如果是刚刚申请的域名,需要做...
用户需求和云的发展两条线推动了云原生技术的兴起、发展和大规模应用。本文将主...
一、前言 为了实现基于微服务开发的产品,或者说为了将单体应用重构为微服务架构...
背景 如果要通过 直接在浏览器中输入域名,访问网站或Web应用程序, 您需要注册...