题目描述

剑指 Offer 11. 旋转数组的最小数字

难度简单

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

示例 1：

输入：[3,4,5,1,2]
输出：1

示例 2：

输入：[2,2,2,0,1]
输出：0

注意：本题与主站 154 题相同：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/

测试用例

• 功能测试（输入的数组是非递减排序数组的一个旋转，数组中有重复的数字或者没有重复的数字）
• 边界值测试（输入的数组是一个非递减排序的数组，只包含一个数字的数组）
• 特殊输入测试（输入空指针）

题目考点

• 考察应聘者对二分查找的理解。如果遇到从排序的数组中查找数字需要尝试二分查找法。
• 考察应聘者的沟通能力和学习能力。如果面试官提出新的概念，那么我们可以主动和面试官沟通，多问几个问题，把概念弄清楚。
• 考察应聘者思维的全面性。排序数组本身是一个数组旋转的一个特例，另外，我们需要考虑到数组中有相同数字的特例。

解题思路

如果遇到从排序的数组中查找数字需要尝试二分查找法。

我们利用两个指针分别指向数组的第一个元素和最后一个元素，我们可以先找到数组中间的元素，如果该中间元素大于或等于第一个元素，则位于前面的非递减子数组，此时我们就可以把第一个指针指向该中间元素，这样就可以缩小寻找的范围，移动以后，第一个指针依然指向前面的非递减数组；否则属于后面的非递减子数组，此时我们就可以把第二个指针指向该中间元素，移动以后，第二个指针依然指向后面的非递减数组。然后循环下去，最终第一个指针将指向前面子数组的最后一个元素，而第二个指针将会指向后面子数组的第一个元素，而第二个指针指向的刚好是最小的元素。循环结束。

参考解题

/**
 * Author:Viper
 * Data:2021/3/11
 * description:
 */
public class problem11 {
    public int minArray(int[] numbers) {
        int len =numbers.length;
        if(len==0)
            return 0;
        int i=0,j=len-1;
        while(i<j){
            int mid = i+(j-i)/2;
            if(numbers[mid]<numbers[j])
                j=mid;
            else if(numbers[mid]==numbers[j])
                j--;
            else
                i=mid+1;
        }
        return numbers[i];
    }
}

补充

如果面试题是要求在排序的数组（或者部分排序的数组）中查找一个数字或者统计某个数字出现的次数， 那么我们都可以尝试 二分查找算法。

强烈建议在准备面试的时候，一定要对各种排序算法的特点烂熟于胸，能够从额外空间消耗、平均时间复杂度和最差时间复杂度等方面去比较他们的优缺点。（特别关注手写快排）

快排算法思想如下：
先在数组中选择一个数字，接下来吧数组中的数字分为两部分，比选择的数字小的数字移到数组的左边，比选择的的数字大的数字移到数组的右边 （善用指针的想法）。然后左右两侧分别递归得到最后结果。

快排算法代码如下：

import java.util.Random;

/**
 * 快速排序
 */
public class QuickSort {

    /**
     * 交换数组中的两个值
     * @param array
     * @param a
     * @param b
     */
    public static void swap (int[] array, int a, int b) {
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }


    /**
     * 分区函数
     * 按随机出的基准值分区，将比基准值小放在基准值左边，大的放在基准值右边
     * @param data
     * @param length
     * @param start
     * @param end
     * @return
     * @throws Exception
     */
    public static int partition(int data[], int length, int start, int end) throws Exception {

        Random random = new Random();

        if (data == null || length <=0 || start <0 || end >= length) {
            throw new Exception("Invalid Parameters");
        }

        // 尽量避免极端情况，每次都是以最后一个数字作为基准值，在start和end之间随机出一个数
        int index = start + random.nextInt(end - start + 1);

        // 将比较的值放在数组的最后
        swap(data, index, end);

        // 定义一个指针，指向所有换序之后所有比基准值都小的数据的最右边，最后最指向基准值应该在位置
        int small = start - 1;

        for (int i = start; i < end; i++) {
            if (data[i] < data[end]) {
                small++;
                // 避免原来就是有序数列的无用交换
                if (small != i) {
                    swap(data, small, i);
                }
            }
        }
        // 把基准值放在中间
        small++;
        swap(data, small, end);
        return small;
    }

    /**
     * 利用分区函数实现快速排序
     * 递归
     * @param data
     * @param length
     * @param start
     * @param end
     * @throws Exception
     */
    public static void quickSort(int[] data, int length, int start, int end) throws Exception {
        // 当只剩一个数的时候就不用递归了
        if (start == end) {
            return;
        }
        int index = partition(data, length, start, end);
        // 防止异常
        if (index > start) {
            quickSort(data, length, start, index - 1);
        }
        if (index < end) {
            quickSort(data, length, index + 1, end);
        }

    }
  }