题目描述：

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

思路：

1.遍历整个数组，找到最小值，通过比较找到最小值，该方法太蛮力。

2.根据数组是非减排序数组旋转得来，可以在遍历的时候优化一下，遍历直到a[i]>a[i+1];此时a[i+1]就是最小值，输出即可。

3.思路2最好情况遍历一次，最差情况遍历n次，我想到一种思路：

　　　　假设旋转后的数组为array[]，其最大索引为end，最小值为min将数组按min的左右分为左区和右区，

　　　　其中左区满足两个条件： array[i] > array[end]    限制了该元素在左边

　　　　　　　　　　　　　　　 array[i] <= array[i + 1] 限制了该元素不是左区的边界值

　　　　其中右区满足两个条件： array[i] < array[0]      限制了该元素在右边

　　　　　　　　　　　　　　　 array[i] >= array[i – 1] 限制了该元素不是右区的边界值

        因此除了上述情况就只剩下左区边界和右区边界了，就很好得到最小值了。

具体代码：

 1 public class test6 {
 2     public static void main(String[] args) {
 3         int arr[] = new int[] { 4, 5, 6, 7, 8, 8, 9, 10, 2, 2, 3 };//此处只列举一种情况为了方便
 4         int a = minNumberInRotateArray(arr);
 5         System.out.println(a);
 6     }
 7 
 8     public static int minNumberInRotateArray(int[] array) {
 9         int a = 0;// 变量记录待返回的最小数
10         if (array.length == 0)// 如果数组为空返回0
11             return a;
12         int i = array.length / 2;
13         while (i > 0 && i < array.length) {// 在左区内
14             if (array[i] > array[array.length - 1] && array[i] <= array[i + 1]) {
15                 i++;
16             } else if (array[i] < array[0] && array[i] >= array[i - 1]) {// 在右区内
17                 i--;
18             } else { // 正好是左区或右区的边界，不满足是左区内或右区内了
19                 // 此时拿到的array[i]是边界值，可能是左区的最大值或右区的最小值，判断一下即可
20                 a = array[i] > array[i + 1] ? array[i + 1] : array[i];
21                 break;
22             }
23         }
24         return a;
25 
26     }
27 }

总结：

最后一种思路效率较高

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

版权声明：本文为zclun原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/zclun/p/9985969.html