旋转数组的最小数字
1、题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
2、我的解答：
import java.util.ArrayList; /* 本题考察重点：分类思想 非减排序即包括递增排序和全等 */ public class Solution { public int minNumberInRotateArray(int [] array) { int count = 0; int result = 0; if(array.length==0){ return result; } for(int i=0;i<array.length-1;i++){ if(array[i]>array[i+1]){ result = array[i+1]; } if(array[i]==array[i+1]){ count++; } } if(count==array.length){ result = array[0]; } return result; } }
3、思考：我的解答没有考虑到旋转数组和原数组相同的情况，而且从头开始对数组进行遍历，时间复杂度O(n)。
4、优质解答：
1）内置排序工具
利用 Arrays 工具类里的排序函数，内置实现是三项切分快排，默认的排序规则是从小到大，排序后的数组第一个值就是最小值
代码：
import java.util.*; public class Solution { public int minNumberInRotateArray(int [] array) { int n = array.length; if(n == 0){ return 0; } Arrays.sort(array); return array[0]; } }
2）二分查找
a. 注
非递减序列并不能找到最小值，因为对于{3, 3, 3, 3, 3, 1, 3} 和 {3, 1,3, 3, 3, 3, 3}，二分法并不能判断范围向哪边收缩
b. 分析
二分查找用于查找有序的数组中的值，题目所给数组在两段范围内有序，我们可以将给定数组分为两种情况：
其实并没有旋转，例如 {1,2,3,4,5}，旋转后也是 {1,2,3,4,5}，这样可以直接使用二分查找
如题所示，旋转了一部分，例如 {1,2,3,4,5}，旋转后为 {3,4,5,1,2}，需要限定特殊条件后使用二分查找
当数组如情况 1，有个鲜明的特征，即数组左边元素 < 数组右边元素，这时我们直接返回首元素即可
当数组如情况 2，此时有三种可能找到最小值：
标为 n+1 的值小于下标为 n 的值，则下标为 n+1 的值肯定是最小元素
下标为 n 的值小于下标为 n-1 的值，则下标为 n 的值肯定是最小元素
由于不断查找，数组查找范围内的值已经全为非降序（退化为情况1）
再讨论每次二分查找时范围的变化，由于情况数组的情况 1 能直接找到最小值，需要变化范围的肯定是情况 2：
当下标为 n 的值大于下标为 0 的值，从 0 到 n 这一段肯定是升序，由于是情况 2，最小值肯定在后半段
当下标为 n 的值小于下标为 0 的值，从 0 到 n 这一段不是升序，最小值肯定在这一段
c. 代码
import java.util.*; public class Solution { public int minNumberInRotateArray(int [] nums) { if (nums.length == 1) { return nums[0]; } int l = 0; int r = nums.length - 1; while (l <= r) { int mid = l + (r - l) / 2; if (nums[l] < nums[r]) { return nums[l]; } if (nums[mid] > nums[mid + 1]) { return nums[mid + 1]; } if (nums[mid] < nums[mid - 1]) { return nums[mid]; } if (nums[mid] > nums[0]) { l = mid + 1; } else { r = mid - 1; } } return 0; } }
d. 复杂度
时间复杂度：O(logn)
空间复杂度：O(1)
原文：https://www.cnblogs.com/JimShi/p/11352366.html