剑指offer（6）——C++实现查找旋转数组中的最小值

谁借莪１个温暖的怀抱￠ 2021-10-29 08:32 291阅读 0赞

# 题目 #

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

# 考察点 #

*  二分查找
 *  思考问题的全面性

# 解题思路 #

设定两个指针分别指向数组首尾，因为旋转不失一般性的会存在两个升序数组，找到这两个升序数组的分界点即可。

# 完整代码 #

/*06-查找旋转数组中的最小数字*/
    #include<iostream>
    #include<vector>
    using namespace std;
    
    class Solution {
        
    public:
    	int minNumberInRotateArray(vector<int> rotateArray) 
    	{
        
    		int length = rotateArray.size();//设定两个指针，指向数组首尾
    		int pstart =0;                  //该指针为数组索引而非数组值
    		int pend = length - 1;         // 方便后边循环判定索引间的关系
    
    		while (pstart<pend)
    		{
        
    			if (rotateArray[pstart] < rotateArray[pend])//旋转个数为0，即未旋转时，数组第一个数即为最小数
    				return rotateArray[pstart];
    
    			int mid = pstart + (pend - pstart) / 2;//等价于(pstart+pend)/2
    			if (rotateArray[mid] > rotateArray[pstart])//中值为升序数组，最小值在其左
    				pstart = mid + 1;
    			else if (rotateArray[mid] < rotateArray[pend])//中值为降序数组，最小值在其右
    				pend = mid;
    			else//此时左右中 三个值相等，将pstart顺序往前推去查找
    				++pstart;
    		}
    		return rotateArray[pstart];
    	}
    };
    
    int main()
    {
        
    	Solution s;
    	vector<int> rotateArray = {
         1,0,1,1,1 };
    	cout << s.minNumberInRotateArray(rotateArray) << endl;
    	return 0;
    }

# 编程中出现的问题 #

*  两个指针一般设定为数组的索引而非数组值，方便后续比较与更改
 *  考虑问题的全面性：非递减就表示可能会存在相同数字如\{1,0,1,1,1\}当比较中间值与首尾值的大小来说明升序时，就会因为三者相等二无法判定，此时就要顺延一位，改变这种状况。