剑指offer11:旋转数组的最小数字

我不是女神ヾ 2022-02-18 20:11 177阅读 0赞

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

思路：

1.直接点，没办法的情况用个快速排序把。第一元素就是快速排序。

2.思路，本身数组就是有序，就算是旋转了，2个子序列依旧是递增的，借用的二分查找的思想。

p1指向指针的第一个元素，p2指向了最后一个元素，当数组nums\[p1\]>=nums\[p2\]依旧循环，如果当p2-p1==1时，那么肯定找到了，p2就是最小的，如果不是这个条件，mid = （p1+p2）/2,当nums\[mid\]>=nums\[p1\],必然在第一个递增序列中，所以p1 = mid;

如果nums\[mid\]<=nums\[p2\]那么index2 = mid; 当序列有特殊情况时，\[1,0,1,1,1\]或者\[1,1,1,0,1\] 就是nums\[p1\]==nums\[p2\]==nums\[mid\]时，那么这样的话，就无法移动指针来缩小范围。只好在这个特殊情况下进行顺序查找。

package com.hnist.lzn.jinazhioffer;
    
    public class Twoorete {
    
        public int solution(int[] nums,int numbers) throws Exception {
    
    
            if(nums==null||nums.length<=0){
    
                throw new Exception("error");
            }
    
            int index1 = 0;
    
            int index2 = nums.length-1;
    
            int indexMid = index1;
    
            while(nums[index1]>=nums[index2]){
    
    
                if(index2-index1==1){
    
                    indexMid = index2;
                    break;
                }
    
                indexMid =(index1+index2)/2;
    
                if(nums[index1]==nums[index2]&&nums[indexMid]==nums[index1]){
    
    
                    return MinOrder(nums,index1,index2);
                }
    
    
                if(nums[indexMid]>=nums[index1]){
                    index1 = indexMid;
                }
    
                if(nums[indexMid]<=nums[index2]){
                    index2 = indexMid;
                }
    
    
    
    
            }
    
                return nums[indexMid];
    
    
    
        }
        public int MinOrder(int[] nums,int index1,int index2)
        {
    
            int result = nums[index1];
    
            for(int i=index1+1;i<index2;i++){
    
                if(result>nums[i]){
    
                    result=nums[i];
                }
    
    
            }
            return result;
        }
    
    
        public static void main(String[] args) throws Exception {
    
            int[] nums = {1,0,1,1,1};
    
            System.out.println(new Twoorete().solution(nums,nums.length));
    
    
        }
    }