剑指offer（C++）——旋转数组的最小数字

比眉伴天荒 2022-06-17 10:20 130阅读 0赞

## 题目描述 ##

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

**思路分析：**

最直观的解法就是从头到尾遍历一遍数组，找出最小数字。时间复杂度为O(n)。但是这个思路没有充分利用旋转数组的特性。

通过观察可以发现旋转数组可以分为两个排序的子数组，前面的子数组元素都大于或等于后面子数组元素。而且最小的数字就是后面子数组的第一个元素。处于两个子数组的分界线处。因此我们可以采用二分查找法实现O(logn)的查找。设置两个指针index1和index2分别指向前一个子数组的开头和后一个子数组的结尾。当中间元素大于index1指向的元素时，证明最小数字位于中间元素的后面，将index1指向中间元素；如果中间元素小于或等于index2指向的元素，则最小数字位于中间元素的前面，将index2指向中间元素（有一种特殊情况，稍后分析）。重复新一轮的查找，直到index1与index2相差1时结束，此时最小值就是index2指向的数字。

**特殊情况：**

例如\{1，0，1，1，1\}和数组\{1，1，1，0，1\}都可以看成是排序数组\{0，1，1，1，1\}的旋转。

对于这个数组旋转，当第一个数字、最后一个数字和中间数字都是1，我们无法判定中间数字1是位于前一个子数组还是 后一个子数组，此时只能用顺序查找法。

实现代码如下：

class Solution {
    public:
    	//基于二分查找算法的快速解法
    	int minNumberInRotateArray(vector<int> rotateArray) {
    		if (rotateArray.empty())
    			return 0;
    		else
    		{
    			int index1 = 0;
    			int index2 = rotateArray.size() - 1;
    			int indexMid = index1; //当把数组前面0个元素搬到后面时，即排序数组本身，第一个数字就是最小数字，可以直接返回
    			while (rotateArray[index1] > rotateArray[index2])
    			{
    				if (index2 - index1 == 1)
    				{
    					return rotateArray[index2];
    					break;
    				}
    				indexMid = (index1 + index2) / 2;
    				if (rotateArray[indexMid] >= rotateArray[index1])
    					index1 = indexMid;
    				if (rotateArray[indexMid] <= rotateArray[index2])
    					index2 = indexMid;
    
    				//当index1、index2和indexMid位置的值相等时，无法判断indexMid属于前半部分还是后半部分，需要遍历查找
    				if (rotateArray[index1] == rotateArray[index2] && rotateArray[index1] == rotateArray[indexMid])
    					return minInorder(rotateArray, index1, index2);
    			}
    			return rotateArray[indexMid];
    		}
    	}
    
    	/*实现顺序查找*/
    	int minInorder(vector<int> Array, int index1, int index2)
    	{
    		int result = Array[index1];
    		for (int i = index1+1;i <= index2;i++)
    		{
    			if (Array[i] < result)
    				result = Array[i];
    		}
    		return result;
    	}
    };