剑指 Offer 11. 旋转数组的最小数字

ゝ一纸荒年。 2022-12-17 01:21 98阅读 0赞

# 题目 #

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 \[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

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof][https_leetcode-cn.com_problems_xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof]

# 解题思路 #

本题需要关注的点:

*  递增排序的数组旋转
 *  数组可能存在重复的元素

主要思路是使用二分法

*  初始数组的左右边界left,right
 *  计算中间下标mid = left + ((right - left) >> 1)
 *  比较arr\[mid\]和arr\[right\]值的大小
    
     *  arr\[mid\] > arr\[right\], 此时旋转发生在mid的右边,且arr\[mid\]肯定不是最小值,left = mid + 1
     *  arr\[mid\] < arr\[right\], 此时旋转发生在mid的左边,且arr\[mid\]有可能为最小值,right = mid
     *  arr\[mid\] = arr\[right\], 此时无法确定,解决方案是右边界左移,保证最小值还在边界中即可,right = right - 1

为什么不用arr\[mid\]和arr\[left\]比较?  
当arr\[mid\] > arr\[left\]的时候,无法判断旋转点,即最小值在mid的左边还是在mid的右边

# 代码 #

class Solution { 
        public int minArray(int[] numbers) { 
            int left = 0;
            int right = numbers.length - 1;
            // 迭代, 终止条件: left == right
            while (left < right) { 
                // 二分法
                int mid = left + ((right - left) >> 1);
                if (numbers[mid] > numbers[right]) { 
                    // 中值大于右边界的值,旋转在右边且当前值肯定不为最小值
                    left = mid + 1;
                } else if (numbers[mid] < numbers[right]) { 
                    // 中值小于右边界的值,旋转在左边且当前值有可能为最小值
                    right = mid;
                } else { 
                    // 中值等于,右边界左移
                    right--;
                }
            }
            return numbers[left];
        }
    }

[https_leetcode-cn.com_problems_xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof]: https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof