剑指offer-牛客网旋转数组的最小数字

一时失言乱红尘 2022-05-09 08:06 74阅读 0赞

这种题其实弄明白原理后就很简单  
    和二分查找差不多，二分查找就是每次都能排除一半的范围，所以复杂度  
    为logn. 先上简单的二分查找代码吧

int left=0,right=array.length-1;
            while(left<right){
                int mid=(left+right)>>1;
                if(array[mid]==target)
                     return mid;
                if(array[mid]<target)
                    left=mid+1;
                else
                    right=mid
            }
            return -1;
        }

有几个点我经常犯错，就是left，right（这里的right指针是开区间，也就是数组末尾）  
前进或后退要注意会不会陷入死 循环。  
（ps：以上代码还没调试过）  
同样思路坐下题目，先把题目贴一下

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

这道题就简单多了，只要考虑mid位置的数就行了，因为只有一种情况  
比较特殊，就是array\[mid\]<array\[left\],这就能确定mid是在后面那一部分，  
right移到mid就行了（这里right不一定是重复值里的最小位置）贴上代码

package 剑指offer;
    
    /**
     * Created by Administrator on 2018/10/4.
     */
    public class Solution06 {
        public static int minNumberInRotateArray(int [] array) {
            int left=0,right=array.length-1;
            while(left<right-1){
                int mid=(left+right)>>1;
                if(array[mid]<array[left])
                    right=mid;
                else
                    left=mid;
            }
            int res=array[left]<array[right]?left:right;
            return array.length==0?0:array[res];
        }
    
        public static void main(String[] args){
            /*int[] array={6501,6828,6963,7036,7422,7674,8146,8468,8704,8717,9170,
                    9359,9719,9895,9896,9913,9962,154,293,334,492,1323
                    ,1479,1539,1727,1870,1943,2383,
                    2392,2996,3282,3812,3903,4465,4605,4665,
                    4772,4828,5142,5437,5448,5668,5706,5725,6300,6335};*/
            int[] array={6,1,1,1,1,1,2,2,2,3,3,4,5};
            System.out.println(minNumberInRotateArray(array));
        }
    }

if(array\[mid\]<array\[left\])  
right=mid;  
这一步我之前是这样的，  
if(array\[mid\]<=array\[left\])  
right=mid;

但这是错的，只要数组是这样int\[\] array=\{6,6,6,6,6,1,2,2,2,3,3,4,5\};  
最小值左边有n个相同的值right就会移向左边过去