剑指Offer RotateArray 旋转数组的最小数字-白红宇

剑指Offer RotateArray 旋转数组的最小数字

阅读量：4208 次

发布时间：2019-05-26

本文共 2046 字，大约阅读时间需要 6 分钟。

题目描述：

把一个数组最开始的若干个元素搬到数组的末尾我们称之为数组的旋转

输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素

思路：

分析旋转数组的特点，例如{3,4,5,1,2}，因为是旋转数组，因此不存在数组整个是递增序列。

最小元素的左边的是比它大的数且依次递增，右边同样的是比它大的递增序列，因此可以使用二分查找，三个指针分别指向首元素、尾元素和中间元素。

当中间元素大于数组首元素，证明从数组起始到中点的元素都是递增的，因此最小元素存在数组的后半部分，继续在后半部分使用二分查找。

当中间元素大于队尾元素证明从数组中点到队尾都是递增序列，最小元素存在数组的前半部分，继续在前半部分使用二分查找

特殊情况当三个指针大小相等无法判断最小元素所在的区域因此此时采用一般的遍历查找方法

public static int minElementInRotateArray(int[] array) {        int leftIndex = 0, rightIndex = array.length - 1, midIndex = (rightIndex + leftIndex) / 2;        while (leftIndex < rightIndex - 1) {            if (array[leftIndex] == array[midIndex] && array[rightIndex] == array[midIndex]) {                //三者相同 无法判断 因此进行顺序查找                return minElementBySort(array);            } else {                if (array[midIndex] >= array[leftIndex]) {                    leftIndex = midIndex;                } else {                    rightIndex = midIndex;                }                midIndex = (rightIndex + leftIndex) / 2;            }        }        return array[rightIndex];    }    private static int minElementBySort(int[] ints) {        int minElement = ints[0];        for (int i = 1; i < ints.length; i++) {            if (ints[i] < minElement) {                minElement = ints[i];            }        }        return minElement;    }

测试：

@RunWith(Parameterized.class)public class RotateArrayTest extends BaseTest {
       @Parameterized.Parameters    public static List
   
     data() {        List
    
      data = new ArrayList<>();        data.add(new Object[]{
  new int[]{
  3, 4, 5, 1, 2}, 1});        data.add(new Object[]{
  new int[]{
  1, 1, 1, 2, 0}, 0});        data.add(new Object[]{
  new int[]{
  1, 0, 1, 1, 1}, 0});        return data;    }    private final int[] array;    private final int min;    public RotateArrayTest(int[] array, int min) {        this.array = array;        this.min = min;    }    @Test    public void test() throws Exception {        int result = RotateArray.minElementInRotateArray(array);        assertEquals(min,result);    }}