1. 题目

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

2. 示例

示例1：

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

示例2：

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

3. 题解

限制条件：

子节是递增的。

思考：

1. 最简单的方法，对数组排序，然后选第一个，但这样做就没得意义了。

2. 对于有序的数组，常规采用的就是二分查找。以下为使用二分朝查找的原理：

• 获取low，middle，high三个index的元素，用middle的元素与high进行比较；
• 可能三种情况：
• numbers[middle] < numbers[high]，说明最小元素存在于左部分，右部分舍去，high = middle；
• numbers[middle] > numbers[high]，说明最小元素存在于右部分，左部分舍去，low = middle + 1；
• numbers[middle] = numbers[middle], 此时无法判断，那么将high-1即可。

3. 偏向于暴力方法，用测试用力发现，这种方法更高效，可能是数据量比较少。

• 判断第一个元素和最后一个元素，若第一个元素大于等于最后一个元素，说明最小元素在中间；
• 此时只要遍历数组，找到第一个当前元素小于前一个元素就是最小元素。

4. 实现

二分查找

 1 public int minArrayA(int[] numbers) {
 2         int low = 0, high = numbers.length - 1;
 3         while (low < high) {
 4             int middle = low + (low + high) / 2;
 5             if(numbers[middle] < numbers[high]) {
 6                 high = middle;
 7             } else if(numbers[middle] > numbers[high]) {
 8                 low = middle + 1;
 9             } else {
10                 high -= 1;
11             }
12         }
13         return numbers[low];
14 }

 

暴力法

1 public int minArray(int[] numbers) {
2         if(numbers.length < 2) return numbers[0];
3         if(numbers[0] >= numbers[numbers.length - 1]) {
4             for(int i = 1; i < numbers.length; i++) {
5                 if(numbers[i] < numbers[i - 1]) return numbers[i];
6             }
7         }
8         return numbers[0];
9     }

5. 结语

　　努力去爱周围的每一个人，付出，不一定有收获，但是不付出就一定没有收获！ 给街头卖艺的人零钱，不和深夜还在摆摊的小贩讨价还价。愿我的博客对你有所帮助(*^▽^*)(*^▽^*)！

　　如果客官喜欢小生的园子，记得关注小生哟，小生会持续更新(#^.^#)(#^.^#)。