旋转数组的最小数字
题目描述
把一个数组最开始的若干个搬到数组的末尾，我们称之为数组的旋转。输入一个非递减数组的旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0.
代码格式要求
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
}
}
非递减数组是指一个数组中的元素要么递增要么相等。
解题一 -暴力法直接查找
1.思路
在一个非递减组数的旋转数组中，只需判断如果前一个数组大于后一个数组，那么后一个数组即为要找的旋转数组中的最小元素。如果旋转数组{6,7,1,3,4,4}，当7大于1时，即可判断出1位数组的最小元素。
2.代码
package jianzhi_offer;
public class Solution6_1 {
public static int minNumberInRotateArray(int[] array) {
int n=array.length;
if(n==0) {
return 0;
}
for(int i=0;i<n-1;i++) {
if(array[i]>array[i+1]) {
return array[i+1];
}
}
return array[0];
}
public static void main(String[] args) {
int[] a= {8,9,2,3,5};
System.out.println(minNumberInRotateArray(a));
}
}
运行结果
3.复杂度
时间复杂度：O(n)
空间复杂度：O(1)
解题二-排序
1.思路
利用 Arrays 工具类里的排序函数，默认的排序规则是从小到大，排序后的数组第一个值就是最小值。
*通过题意可以了解到，只需要输出旋转后数组最小元素就行了，所以直接给数组进行排序
*数组的一个元素就是最小元素，最后输出即可，Arrays.sort()的排序时间复杂度是根据数组长度来判断
*基本类型是quick sort排序，对象类型是优化过后 merge sort，时间复杂度是O(nlgn) 空间复杂度O(1)
2.代码
import java.util.Arrays;
public class Solution6_2 {
public int minNumberInRotateArray(int[] array) {
int n=array.length;
if(n==0) {
return 0;
}
Arrays.sort(array);
return array[0];
}
}
3.复杂度
时间复杂度：O(nlogn)
空间复杂度：O(1)
解题三-利用优先队列
1.思路
将数组元素挨个放进优先队列，优先队列默认为最小堆，弹出的第一个数就是整个数组的最小值。
2.代码
import java.util.PriorityQueue;
//优先队列
public class Solution6_3 {
public int minNumberInRotateArray(int[] array) {
if(array.length==0) {
return 0;
}
PriorityQueue<Integer> queue=new PriorityQueue<Integer>();
for(int i=0;i<array.length;i++) {
queue.add(array[i]);
}
return queue.poll();
}
}
- 复杂度
时间复杂度：O(n)
空间复杂度：O(n)
解题四-二分查找法
1.解析
本题的一个简单算法就是从左到右遍历，由于是递增的，直到找到一个小的数就可以停止了但是这种方法速度相对太慢，所以可以采用二分法的思想采用二分法的思想，定义一个left和right逐步缩小范围，最终确定最小的数.
2.代码
package jianzhi_offer;
//二分排序
public class Solution6_4 {
public static int minNumberInRotateArray(int[] array) {
if(array.length==0) {
return 0;
}
///定义左边界
int left=0;
//定义右边界
int right=array.length-1;
//当左小于右的时候，说明范围还没缩小完毕
while (left<right) {
int mid=(left+right)/2;
//如果大于的话，说明最小值在右边，更新左边界值
if(array[mid]>array[right]) {
left=mid+1;
//判断是否等于，让right-1，继续遍历
}else if(array[mid]==array[right]){
right=right-1;
}else {
//判断是否小于，小于的话更新有边界值
right=mid;
}
}
//最后返回right或者left
return array[right];
}
public static void main(String[] args) {
int []a= {3,4,5,1,2};
System.out.println(minNumberInRotateArray(a));
}
}
- 复杂度
时间复杂度：O(logn)
空间复杂度：O(1)
二分查找法
参考解答区“leetcold”的解答，进行图示分析
分析：二分查找变种，没有具体的值用来比较。那么用中间值和高低位进行比较，看处于递增还是递减序列，进行操作缩小范围。
- 处于递增：low上移
- 处于递减：high下移（如果是
high-1，则可能会错过最小值，因为找的就是最小值）- 其余情况：low++缩小范围
- 特殊情况：
代码
`int` `minNumberInRotateArray(vector<``int``> rotateArray) {`
`if``(rotateArray.empty())`
`return` `0``;`
`int` `low =` `0``;`
`int` `high = rotateArray.size() -` `1``;`
`int` `mid =` `0``;`
`while``(low < high){`
`// 子数组是非递减的数组，10111`
`if` `(rotateArray[low] < rotateArray[high])`
`return` `rotateArray[low];`
`mid = low + (high - low) /` `2``;`
`if``(rotateArray[mid] > rotateArray[low])`
`low = mid +` `1``;`
`else` `if``(rotateArray[mid] < rotateArray[high])`
`high = mid;`
`else` `low++;`
`}`
`return` `rotateArray[low];`
`}`
