06 旋转数组最小值

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

第一遍读题没想明白…看了下题解后发现自己想复杂了…

首先用for循环写了个答案…没想到竟然通过了…时间复杂度毕竟 $O(n)$

import java.util.ArrayList; public class Solution { public int minNumberInRotateArray(int [] array) { int n = array.length; if(n==0){ return -1; } for(int i = 0; i < n-1; i++ ){ if(array[i]>array[i+1]){ return array[i+1]; } } return array[n-1]; } }

第二种解法…第一次使用的优先队列（PriorityQueue）…

优先级队列在添加元素的时候会自动有序把元素进行排列。默认是升序。

常用方法 1.add(e)

2.element()、peek()

element()和peek()的语义完全相同，都是获取但不删除队首元素，也就是队列中权值最小的那个元素，二者唯一的区别是当方法失败时前者抛出异常，后者返回null。根据小顶堆的性质，堆顶那个元素就是全局最小的那个；由于堆用数组表示，根据下标关系，0下标处的那个元素既是堆顶元素。所以直接返回数组0下标处的那个元素即可。

3.remove()、poll()

remove()和poll()方法的语义也完全相同，都是获取并删除队首元素，区别是当方法失败时前者抛出异常，后者返回null。由于删除操作会改变队列的结构，为维护小顶堆的性质，需要进行必要的调整。

import java.util.ArrayList; public class Solution { public int minNumberInRotateArray(int [] array) { int n = array.length; if(n == 0){ return 0; } PriorityQueue<Integer> queue = new PriorityQueue<>(); for(int i = 0;i<n;i++){ queue.add(array[i]); } return queue.roll(); } }

时间复杂度一样，但是空间复杂度 $O(n)$

…就当练习下优先队列

因为是分段有序…考虑下使用二分查找、

import java.util.ArrayList; public class Solution { public int minNumberInRotateArray(int [] array) { } }