题解 | 旋转数组的最小数字

1、解题思路

1. 二分查找：虽然数组旋转后不再完全有序，但可以利用二分查找的思想快速定位最小值。比较中间元素 nums[mid] 与右边界 nums[right] ： 如果 nums[mid] < nums[right]，最小值在左侧（包括 mid）。如果 nums[mid] > nums[right]，最小值在右侧（mid + 1 到 right）。如果 nums[mid] == nums[right]，无法确定最小值在哪侧，此时可以缩小右边界 right--。
2. 关键点：最小值位于旋转点，即第一个小于前一个元素的元素。由于数组是非降序的，旋转后的数组仍保持部分有序性。

2、代码实现

C++

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型vector
     * @return int整型
     */
    int minNumberInRotateArray(vector<int>& nums) {
        // write code here
        int left = 0, right = nums.size() - 1;

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

        return nums[left];
    }
};

Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型
     */
    public int minNumberInRotateArray (int[] nums) {
        // write code here
        int left = 0;
        int right = nums.length - 1;

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

        return nums[left];
    }
}

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型
#
class Solution:
    def minNumberInRotateArray(self , nums: List[int]) -> int:
        # write code here
        left, right = 0, len(nums) - 1
        
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] < nums[right]:
                right = mid
            elif nums[mid] > nums[right]:
                left = mid + 1
            else:
                right -= 1
                
        return nums[left]

3、复杂度分析

• 空间复杂度：O(1)
• 时间复杂度：O(logn)