leetcode 链接：旋转数组的最小数字

题目

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

示例：

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

解答 & 代码

image.png
image.png
image.png
image.png

class Solution {
public:
    int minArray(vector<int>& numbers) {
        int left = 0;
        int right = numbers.size() - 1;

        // 特殊情况：如果最左边元素小于最右边元素，说明数组未旋转，仍是递增的，直接返回最左边元素
        // 注意：由于数组中可以包含重复元素，因此如果最左边元素等于最右边元素，无法判断数组是否递增
        if(numbers[left] < numbers[right])
            return numbers[left];

        // 二分查找
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            // case1：numbers[mid] < numbers[right]，说明 numbers[mid] 是最小值右侧（含最小值本身）的元素
            // 因此忽略二分查找的右半区间，到左半区间继续查找
            // 因为 numbers[mid] 本身可能就是最小值，因此令 right=mid，而不是 mid-1
            if(numbers[mid] < numbers[right])
                right = mid;
            // case2：numbers[mid] > numbers[right]，说明 numbers[mid] 是最小值左侧的元素（肯定不含最小值本身）
            // 因此忽略二分查找的左半区间，到右半区间继续查找
            // 因为 numbers[mid] 本身不可能就是最小值，因此令 left=mid+1
            else if(numbers[mid] > numbers[right])
                left = mid + 1;
            // case3：numbers[mid] == numbers[right]，无法判定 numbers[mid] 在最小值左侧还是右侧
            // 但是因为 numbers[mid] == numbers[right]，因此 numbers[right] 无论是不是最小值，都有重复值
            // 因此可以忽略 numbers[right]
            else
                --right;
        }
        return numbers[left];
    }
};

执行结果：

执行结果：通过

执行用时：4 ms, 在所有 C++ 提交中击败了 91.90% 的用户
内存消耗：11.9 MB, 在所有 C++ 提交中击败了 15.98% 的用户

牛客网链接：JZ6 旋转数组的最小数字

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int len = rotateArray.size();
        if(len == 0)
            return 0;
        if(len == 1)
            return rotateArray[0];

        int left = 0;
        int right = len - 1;
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(rotateArray[mid] < rotateArray[right])
                right = mid;
            else if(rotateArray[mid] > rotateArray[right])
                left = mid + 1;
            else
                --right;
        }
        return rotateArray[left];
    }
};

执行结果：

执行结果：通过

执行用时：4 ms, 在所有 C++ 提交中击败了 96.46% 的用户
内存消耗：564 KB, 在所有 C++ 提交中击败了 85.17% 的用户