求旋转数组后的最小值

川长思鸟来 2022-08-08 12:56 250阅读 0赞

# 题目 #

一个有序数组，将前面的一段放在数组的后面就被称之为旋转。比如\[1,2,3,4,5,6\]就可以旋转为\[5,6,1,2,3,4\]。输入一个旋转后的数组，输出数组中的最小值。

# 思路 #

直接遍历的时间复杂度是O(n)。接下来介绍并实现一个O(log n)的算法。  
以\[50, 10, 20, 30, 40\]为例：  
下标：first = 0, last = 4, mid = 2  
因为array\[mid\] < array\[first\]  
所以，array\[mid+1 … last\] 都大于array\[mid\]。即，mid+1到last这一部分里面没有最小值。这样就可以舍弃一半，类似于二分查找了。

# 代码 #

class Solution {
    public:
        int minNumberInRotateArray(vector<int> rotateArray) {
            int last = rotateArray.size() - 1;
            if(last < 0 )
                return 0;
            if(last == 0)
                return rotateArray[0];
            int first = 0;
            int mid;
            while(last - first > 1){
                mid = (last + first)/2;
                if(rotateArray[mid] > rotateArray[first] && rotateArray[first] > rotateArray[last]){
                    first = mid;
                }
                else if(rotateArray[first] == rotateArray[last]){
                    first++;//针对测试用例7和8
                }
                else if(rotateArray[mid] == rotateArray[first])
                    first++;//针对测试用例6
                else if(rotateArray[mid] == rotateArray[last])
                    last--;//针对测试用例7
                else{
                    last = mid;
                }
            }
            return min(rotateArray[first], rotateArray[last]);
        }
    };

# 测试用例 #

1.  \[1,2,3,4,5,6\]
2.  \[2,3,4,5,6,1\]
3.  \[3,4,5,6,1,2\]
4.  \[6,1,2,3,4,5\]
5.  \[1,2,2,2,2,2\]
6.  \[2,2,2,2,2,1\]
7.  \[2,1,2,2,2,2\]
8.  \[2,2,2,2,1,2\]
9.  \[1\]