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

大佬教程收集整理的这篇文章主要介绍了剑指 Offer 11. 旋转数组的最小数字，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

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. 结语

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

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

大佬总结

以上是大佬教程为你收集整理的剑指 Offer 11. 旋转数组的最小数字全部内容，希望文章能够帮你解决剑指 Offer 11. 旋转数组的最小数字所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。