首页 > 代码库 > 旋转数组的最小数字
旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
第一种思路是：从数组的第一个元素开始看，找到第一个前一个元素比后一个元素大的下标，返回下标值+1所对应的数组元素中的值。时间复杂度：O(n)
public int getMin(int[] array){ int i=0; for(;i<array.length;i++){ if(array[i]>array[i+1]){ break; } } return array[i+1]; }
第二种思路是：运用二分查找的思路来做这件事。先找到数组的中间值，然后和数组的第一个和最后一个元素比较，通常第一个元素都是大于最后一个元素的，若中间元素值大于前面的元素，则最小值肯定在后面的部分，将前面的下标赋给中间小标，若中间的元素值比后面的元素值小，则将后面的元素值赋值给中间的元素。最后，中间的元素值可能等于前面的元素，也可能等于后面的元素，此时，不能判定最小值是在哪一部分，所以需要用顺序法，从头开始判断，找到最小的值。
public int minNumberInRotateArray(int [] array) { if(array[0]<array[array.length-1]){ return array[0]; } int n = array.length; int low = 0; int high = n-1; while(high-low!=1){ int mid = low+(high-low)/2; if(array[mid] == array[low] && array[mid] == array[high]){ return getShunxu(array); } if(array[mid]>=array[low]){ low = mid; }else{ high = mid; } } return array[high]; } public int getShunxu(int[] array){ int min = array[0]; for(int i=1;i<array.length;i++){ if(array[i]<min){ min = array[i]; } } return min; }
旋转数组的最小数字
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。