LeetCode题解之旋转数组的数字

前言

今天继续算法题：旋转数组的最小数字

题目：旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [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  
  
  
  
            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  
  
  
  
            //找到中间点 
  
  
  
  
            int mid=left+(right-left)/2; 
  
  
  
  
            if(numbers[mid]  
  
  
  
                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/

本文转载自微信公众号「 码上积木」，可以通过以下二维码关注。转载本文请联系 码上积木公众号。

文章名称：LeetCode题解之旋转数组的数字
网站路径：http://www.shufengxianlan.com/qtweb/news21/473971.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联