剑指offer——旋转数组的最小数字

【题目】
把一个数组最开始的若干个元素搬到数组的末尾, 我们称之数组的旋转。
输入一个递增排序的数组的一个旋转, 输出旋转数组的最小元素。
例如数组{ 3, 4, 5, 1, 2} 为{ l, 2, 3, 4, 5}的一个旋转,该数组的最小值为 1。
/**
*
* 暴力遍历寻找
*
*二分查找方法:
*1.两个指针指向数组第一个和最后一个元素(第一个元素应该大于等于最后一个元素)
*2.找数组中间的元素,如果中间元素大于等于第一个指针指向的元素,则中间元素位于前面的递增序列,那么最小值应该位于中间元素后面,移动left
*3.如果中间元素小于等于第二个指针指向的元素,则中间元素位于后面的递增序列,那么最小值应该位于中间元素的前面,移动right
*4.如此不断循环,最终两个指针会指向两个相邻的元素,此时第二个指针指向的就是最小元素,这就是循环结束的条件。
*
*为了解决特例:如果将排序数组的前面0个元素搬到最后面,即数组本身,我们初始化mid为left,
*一旦发现数组中第一个元素小于最后一个元素,直接返回一个元素;
*对于{1,0,1,1,1}这样的数组,无法正确查找,也就是左中右三个指针的元素都相同时,只能顺序遍历查找。
*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public class 旋转数组的最小数字 {
    public static int xzsz1(int[] arr) {
        for(int i = 1;i<arr.length-1;i++) {
            if(arr[i-1]>arr[i] && arr[i] < arr[i+1]) {
                return arr[i];
            }
        }
        if(arr[arr.length-1]<arr[arr.length-2]) {
            return arr[arr.length-1];
        }
        return 0;      
    }
    public static int xzsz2(int[] arr) {
        int left = 0;
        int right =  arr.length -1;
        int mid = left;
        while(arr[left] >= arr[right]) {
            if(right - left == 1) {
                mid = right;
                break;
            }
            mid = (left + right)/2;
            if(arr[left] == arr[right] && arr[left] == arr[mid]) {
                return bl(arr,left,right);
            }
            if(arr[mid] >= arr[left]) {
                left = mid;
            }else if(arr[mid] <= arr[right]) {
                right = mid;
            }                          
        }
        return arr[mid];   
    }
   

    private static int bl(int[] arr, int left, int right) {
        int res = arr[left];
        for(int i = left+1;i<right;i++) {
            if(res>arr[i]) {
                res = arr[i];
            }
        }
        return res;
    }
    public static void main(String[] args) {
        int[] arr = {2,3, 4, 5, 1};
        int[] arr2 = {1,1,1,0,1};
        int[] arr3 = {1,0,1,1,1};
        int[] arr4 = {1,2,3, 4, 5};
        System.out.println(xzsz1(arr));
        System.out.println(xzsz2(arr2));
        System.out.println(xzsz2(arr3));
    }

}
0 条评论
发表一条评论