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

待我称王封你为后i 2022-10-17 00:48 137阅读 0赞

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

*  题目难度：简单
 *  方法一：二分查找（减治思想）

> 链接：[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]  
> 来源：力扣（LeetCode）图解算法数据结构

# 题目难度：简单 #

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

模板

class Solution {
        
        public int minArray(int[] numbers) {
        
            
        }
    }

# 方法一：二分查找（减治思想） #

解题思路：

如下图所示，寻找旋转数组的最小元素即为寻找 **右排序数组** 的首个元素  n u m s \[ x \] nums\[x\] nums\[x\] ，称  x x x 为 旋转点 。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70_pic_center]  
排序数组的查找问题首先考虑使用 **二分法** 解决，其可将 **遍历法** 的 **线性级别** 时间复杂度降低至 **对数级别** 。

数组中最特殊的位置是左边位置 `left` 和右边位置 `right`，将它们与中间位置 `mid` 的值进行比较，进而判断最小数字出现在哪里。

用左边位置 `left` 和中间位置 `mid` 的值进行比较是否可以？

*  例如： `[3, 4, 5, 1, 2]` 与 `[1, 2, 3, 4, 5]` ，此时，中间位置的值都比左边大，但最小值一个在后面，一个在前面，因此这种做法不能有效地减治。

用右边位置 `right` 和中间位置 `mid` 的值进行比较是否可以？

*  例如：`[1, 2, 3, 4, 5]`、`[3, 4, 5, 1, 2]`、`[2, 3, 4, 5 ,1]`，**用右边位置和中间位置的元素比较，可以进一步缩小搜索的范围**。

补充说明：遇到 `nums[mid] == nums[right]` 的时候，不能草率地下定结论最小数字在哪一边，但是可以确定的是，把 `right` 舍弃掉，并不影响结果。

public class Solution {
        
    
        // [3, 4, 5, 1, 2]
        // [1, 2, 3, 4, 5]
        // 不能使用左边数与中间数比较，这种做法不能有效地减治
    
        // [1, 2, 3, 4, 5]
        // [3, 4, 5, 1, 2]
        // [2, 3, 4, 5 ,1]
    
        public int minArray(int[] numbers) {
        
            int len = numbers.length;
            if (len == 0) {
        
                return 0;
            }
            int left = 0, right = len - 1;
            while (left < right) {
        
            	// 防止溢出
            	// int mid = left + ((right - left) >> 1);
                int mid = (left + right) >> 1;
                if (numbers[mid] > numbers[right]) {
        
                    // [3, 4, 5, 1, 2]，mid 以及 mid 的左边一定不是最小数字
                    // 下一轮搜索区间是 [mid + 1, right]
                    left = mid + 1;
                } else if (numbers[mid] == numbers[right]) {
        
                    // 只能把 right 排除掉，下一轮搜索区间是 [left, right - 1]
                    right = right - 1;
                } else {
        
                    // 此时 numbers[mid] < numbers[right]
                    // mid 的右边一定不是最小数字，mid 有可能是，下一轮搜索区间是 [left, mid]
                    right = mid;
                }
            }
    
            // 最小数字一定在数组中，因此不用后处理
            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/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70_pic_center]: /images/20221014/801b6220f81b45feac1058ff77f3bd37.png