【剑指offer】面试题11-旋转数组的最小数字

2020-01-23
阅读量 | 字数：539字 | 预计阅读时长：2分钟

题目

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

1.思路

逆序遍历数组，当找到相邻两个元素，满足前一个元素大于后一个元素时，返回后一个元素。
很明显旋转数组的特点是，
①可以将整个数组分为前后两个非递减排序的数组
②而且前一个数组的所有元素都比后一个数组的元素大。
那么只要逆序遍历找到他们的分界线就好啦！~
补充（2020年1月25日 22：23：50）：顺序遍历也可以，找到相邻两个数，前一个恰好比后一个大，这样也是对的，1月23日写博客的时候用的逆序遍历的方法，感觉还是用顺序遍历更便于写代码一些。代码就不补充上了，比逆序要更容易敲。

2.代码（Java实现）

(1)顺序遍历查找–O(n)

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        int len = array.length;
		if(len == 0) {	
	    	return 0;	//数组大小为0，返回0
	    }else {
	    	int res = array[len - 1];	
			for(int i = len - 1; i > 0; i--) {
				if(array[i - 1] > array[i]) {	//找到分界位置
					res = array[i];
					break;
				}
			}
			return res;
	    }
    }
}	//O(n)

(2)二分查找–O(logn)

import java.util.ArrayList;
public class Solution {
	public int minNumberInRotateArray(int [] array) {
		int len = array.length;
		if(len == 0) {	
	    	return 0;	//数组大小为0，返回0
	    }else {
	    	int low = 0; 
	    	int high = len - 1;
	    	int mid = 0;
	    	while (array[low] >= array[high]){
	    		if(high - low == 1) {	//找到分界了
	    			mid = high;	//定位最小元素
	    			break;		//跳出循环
	    		}
	    		mid = low + (high - low) / 2; //防止溢出
	    		//上一句的原型是int mid = （low + high）/ 2	    
	    		if(array[mid] >= array[low]){
	    			low = mid;
	    		}else if(array[mid] <= array[high]){
					high = mid;
				}
	    	}
			return array[mid];
	    }
    }
}

本文作者： whtli
本文链接： https://hexo.whtli.cn/archives/8588f4a0.html
版权声明： 遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。