剑指offer面试题系列

代码

package com.study;

/*
 * 求旋转数组的最小数字
 * 设定：输入递增排序数组的一个旋转
 * 要求返回最小的数
 * */
public class suanfa6 {

    // private static int[] arr = { 7, 8, 9, 10, 11, 3, 4, 5, 6 };
    //private static int[] arr = { 7, 8, 9, 1, 2, 3, 4, 5 };

    private static int[] arr = { 1, 1, 0 , 1};
    // private static int[] arr = {1,0}
    // private static int[] arr = {1,1,1,1,0,1};
    public static int Rotate(int[] arr) {
        int pre = 0;
        int after = arr.length - 1;
        int dif = arr[pre] - arr[after]; // 初始差值
        if (dif < 0 || after - pre < 1) { // 输入不合法
            return -1;
        }

        else if (after - pre == 1) { // 输入的数组只有两个元素
            return arr[after];
        }

        for (pre = 1, after = arr.length - 2; pre <= after; pre++, after--) {
            if (arr[pre] - arr[after] < 0) { // 大数部分和小数部分不对称，要判断在前面的一部分还是后面的一部分

                if (arr[pre - 1] > arr[pre])
                    return arr[pre];
                else
                    return arr[after + 1];
            }

            if (arr[pre] - arr[after] > dif) {
                dif = arr[pre] - arr[after];
            } else {
                return arr[after + 1];
            }
        }
        return -1;
    }

    public static int FindIndex(int[] arr, int pre, int after) {
        int result = arr[pre];
        while (pre <= after) {
            if (arr[pre] < result)
                break;
            pre++;
        }

        return pre;
    }

    public static int RotateNew(int[] arr) {
        /** 利用二分法的思路 */

        int pre = 0;
        int after = arr.length - 1;

        int mid = pre;
        while (arr[pre] >= arr[after]) {
            if (after - pre == 1) {
                mid = after;
                break;
            }

            mid = (pre + after) / 2;

            if (arr[pre] == arr[after] && arr[pre] == arr[mid])
                mid = FindIndex(arr, pre, after);
            if (arr[pre] <= arr[mid])
                pre = mid;
            else if (arr[pre] >= arr[mid])
                after = mid;
        }

        return arr[mid];
        /*
         * int mid = (pre + after) / 2; while (arr[pre] < arr[mid]) { pre = mid;
         * mid = (pre + after) / 2; }
         * 
         * if (arr[pre] > arr[mid]) { while (pre < mid && arr[pre] < arr[pre +
         * 1]) pre++; }
         */
    }

    public static void main(String[] args) {
        System.out.println(RotateNew(arr));
    }
}

说明：

1.Rotate函数是自己做的一版，自己选了多组测试例都通过了，好像没啥问题。但是较为繁琐。思路是通过首尾两个指针，分别往中间靠拢，然后比较首尾之差，我的理解是因为前面部分也递增，后面也是递增，所以差会越来越大，终止条件就是首尾指针碰到一块或者出现了负数，也就是两个指针都跑到一个递增部分了。但是期间，要考虑各种不对称情况，且算法复杂度较高。

2.RotateNew函数是自己参照剑指offer书上的答案写的，算法复杂度降到了O(logN),是二分法的一个发散，相当经典，值得学习。且考虑了 1，0，1，1类似这种非递减序列的情况。

3.注释部分是自己的另一种思路，实现过程中各种问题，还是没有把二分的思路应用到解题中，汗！