leetcode--旋转数组的最小数字（c++）

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

示例 1：
输入：[3,4,5,1,2] 输出：1
示例 2：
输入：[2,2,2,0,1] 输出：0

二分法：

• 当 numbers[m] > numbers[right]时： m 一定在 左排序数组 中，即旋转点 x一定在 [m + 1, right] 闭区间内，因此执行 left = m + 1；
• 当 numbers[m] < numbers[left] 时： m 一定在 右排序数组 中，即旋转点 x一定在[left, m] 闭区间内，因此执行 right= m；
• 当 numbers[m] == numbers[left] 或 numbers[m] == numbers[right] 时： 无法判断 m 在哪个排序数组中，即无法判断旋转点 x 在 [left, m]还是 [m + 1, right]区间中。解决方案： 执行 right = right- 1 缩小判断范围 。

class Solution {
public:
    int minArray(vector<int>& numbers) {
        int left = 0; 
        int right = numbers.size() - 1;
        while(left <  right){
            int mid = (int )(left +  right) / 2 ;
            if(numbers[mid] > numbers[right])
                left = mid + 1 ;
            else if(numbers[mid] < numbers[left] )
                right = mid;
            else 
                right -= 1;
        }
        return numbers[left];
    }
};

暴力法：

数组中的最小值一定是答案。

class Solution {
public:
    int minArray(vector<int>& numbers) {
        int min = numbers[0];
        for(int i = 1; i <= numbers.size() - 1; i++ )
            if( min > numbers[i])
                min = numbers[i];
        return min;
    }
};

最后

以上就是不安裙子为你收集整理的leetcode--旋转数组的最小数字（c++）的全部内容，希望文章能够帮你解决leetcode--旋转数组的最小数字（c++）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。