旋转数组的最小数字

LinkedME2016 发布于2019-08-16 12:35 / 2342人阅读

摘要：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组为的一个旋转，该数组的最小值为。但我们不能区分出最小的数字在的左边还是右边，就没法进行判断了。

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0.

发现用二分法解决这个问题很好，{3,4,5,1,2}可以分成两个排好序的子数组{3,4,5}{1,2}，而左边的每个数一定大于右边的每个数，所以可以声明两个索引left=0，right=length-1，mid=left（为啥这么设置初始值请看代码注释）.
开始循环，循环条件为list[left] >= list[right]。我们要做的事情就是让left一直处于第一个数组里且不断接近第一个数组尾，让right一直处于数组二且不断接近数组二的头。让mid等于（left+right）/2，当mid大于left时，说明此时mid还在第一个数组里，这时就让left=mid；继续循环mid再等于（left+right）/2，假设此时mid小于left了，那么它一定处于第二个数组里了，而且它也小于right（因为right时第二个数组当前最大的）.当left+1==right的时候就可以跳出循环了，因为此时right就是我们要找的元素。

 public class Jianzhi{

    public static void main (String[] args){
        int[] num = {3,4,5,1,2};
        int m = find(num ) ;
        System.out.println(m);
    }
    public static int find(int[] list) {
        if(list == null){  //数组为null时
            return -1 ;
        }
        if(list.length == 0 ){  //数组长度为0则返回0
            return 0 ;
        }
        int left = 0 ;    
        int right = list.length - 1 ;
        int mid = left ;    //注意：这一步让mid等于left是有用意的，如果list是排好序的，
                            //那么直接返回list[mid] 
        while(list[left] >= list[right]){ 
            if(left + 1 == right){
                    return right ;
            }
            mid = (left + right) / 2 ;
            if(list[mid] == list[left] && list[mid] == list[right]){
                return minInOrder(list,left,right);
            }
            if(list[mid] >= list[left]){
                left = mid ;
            }
            if(list[mid] <= list[right] ){
                right = mid  ;
            }
        }
        return list[mid] ;
    }
public static int minInOrder(int[] list , int left , int right ){
    int result = list[left] ;
    for(int i = left+1 ; i < right ; i++){
        if(result > list[i] ){
            result = list[i] ;
        }
    }
    return result ;
}

}

可能大家比较疑惑为什么有以下这句：

if(list[mid] == list[left] && list[mid] == list[right]){
                return minInOrder(list,left,right);
            }

考虑下面这种情况

此时第一个和第二个索引以及mid索引指向的指都是1，三个数字相同。但我们不能区分出最小的数字在mid的左边还是右边，就没法进行判断了。此时，就不得不采用顺序查找方法：

public static int minInOrder(int[] list , int left , int right ){
        int result = list[left] ;
        for(int i = left+1 ; i < right ; i++){
            if(result > list[i] ){
                result = list[i] ;
            }
        }
        return result ;
    }

整个算法最重要的还是让left和right都往两个数组的公共边界靠拢。

完毕。

GPU云服务器云服务器旋转数组数组中未出现的数字二维数组旋转数组最小值

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/71371.html

【剑指offer】7.旋转数组的最小数字

摘要：题目把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组为的一个旋转，该数组的最小值为。出现这种情况的类似，此时最小数字一定在的右边。题目把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,...

W4n9Hu1 2019-08-23 14:48 评论0 收藏0
数据结构与算法（查找和排序） --javascript语言描述

摘要：如此，便可以缩小搜索范围，提高时间复杂度，最终第一个指针指向前面子数组的最后一个元素，而第二个指针指向后面子数组的第一个元素，它们处于相邻位置，而第二个指针指向的刚好是最小的元素。旋转数组的最小数字（二分查找）把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3...

Stardustsky 2019-08-26 11:45 评论0 收藏0
算法练习6：旋转数组的最小数字

摘要：题目有一个长度为的非降序数组，比如，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了，或者这样的。请问，给定这样一个旋转数组，求数组中的最小值。题目:有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，...

DirtyMind 2021-11-25 09:43 评论0 收藏0
剑指Offer(Java版) 持续更新中

摘要：面试题从尾到头打印链表输入一个链表，从尾到头打印链表每个节点的值面试题重建二叉树输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。例如输入前序遍历序列和中序遍历序列，则重建二叉树并返回。队列中的元素为类型。其中负数用补码表示。面试题2 单例(之前有整理，略) 面试题3 二维数组中的查找 public boolean find(int target, int [][] arra...

justCoding 2019-08-15 11:04 评论0 收藏0
70道前端LeetCode题目集合及视频讲解（持续更新中...）

前端LeetCode刷题下面是已刷的题目的目录。GitHub：https://github.com/cunzaizhuy...每日打卡更新中，欢迎关注。数组类 26 删除排序数组中的重复项 27 移除元素 35 搜索插入位置 66 加1 80 medium 删除排序数组中的重复项2 88 合并两个有序数组 167 两数之和II - 输入有序数组 118 杨辉三角 169 easy 求众数 1...

mayaohua 2019-08-26 10:46 评论0 收藏0