剑指11：旋转数组的最小数字

传送门

nowcoder
leetcode

题目描述

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

C++ 代码 - nowcoder

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int n = rotateArray.size();
        if (n == 0) return 0;
        if (n == 1) return rotateArray[0];
        for (int i = 0; i < n - 1; i ++) {
            if (rotateArray[i] > rotateArray[i + 1]) return rotateArray[i + 1];
        }
        return rotateArray[0]; // 说明整个数组都是非递减的
    }  
};

/*
    二分
*/
class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int n = rotateArray.size();
        if (n == 0) return 0;
        
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (rotateArray[mid] < rotateArray[r]) r = mid; // 说明右边有序，向左走
            else if (rotateArray[mid] == rotateArray[r]) r = r - 1; // 特例：只能一个一个判断
            else l = mid + 1;
        }
        
        // return min(rotateArray[l], rotateArray[r]);
        return rotateArray[r];
    }  
};

/*
    二分

    数组中可能存在重复的元素。
    数组中最小值前面的数 nums[i] 都满足：nums[i] >= nums[0]，其中 nums[n−1]是数组最后一个元素，
    而数组中最小值后面的数（包括最小值）都不满足这个条件，所以可以二分出最小值的位置。
    注意：
        1. 删除数组尾部与头部相同的重复元素。
        2. 处理数组完全单调的特殊情况。

    时间复杂度：O(logn)
*/
class Solution {
public:
    int minNumberInRotateArray(vector<int> nums) {
        int n = nums.size() - 1;
        if (n < 0) return -1;
        while (n > 0 && nums[n] == nums[0]) n --;
        if (nums[n] >= nums[0]) return nums[0];
        
        int l = 0, r = n;
        while (l < r) {
            int mid = l + r >> 1;
            // nums[0]，不是 nums[l]
            if (nums[mid] < nums[0]) r = mid; // 说明左边乱序，向左走
            else l = mid + 1; // 说明左边有序，向右走
        }
        
        return nums[r];
    }  
};

C++ 代码 - leetcode

class Solution {
public:
    int minArray(vector<int>& nums) {
        if (nums.size() == 0) return 0;

        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] < nums[r]) r = mid; // 右边有序，向左走
            else if (nums[mid] == nums[r]) r = r - 1; // 特例：只能一个个判断
            else l = mid + 1; // 右边无序，向右走
        }

        // return min(nums[l], nums[r]);
        return nums[r];
    }
};

/*
    增加条件：数组中可能存在重复的元素。

    数组中最小值前面的数 nums[i] 都满足：nums[i] >= nums[0]，
    其中 nums[n−1]是数组最后一个元素，而数组中最小值后面的数（包括最小值）都不满足这个条件。
    所以可以二分出最小值的位置。
    注意：
        1. 删除数组尾部与头部相同的重复元素。
        2. 不要忘记处理数组完全单调的特殊情况。

    时间复杂度：O(logn)
*/
class Solution {
public:
    int minArray(vector<int>& nums) {
        int n = nums.size() - 1;
        if (n < 0) return -1;
        while (n > 0 && nums[n] == nums[0]) n --;
        if (nums[n] >= nums[0]) return nums[0];

        int l = 0, r = n;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] < nums[0]) r = mid; // 说明右边乱序，向左走
            else l = mid + 1; // 说明左边有序，向右走
        }
        return nums[r];
    }
};