剑指Offer11_旋转数组的最小数字

忘是亡心i 2023-10-05 13:12 31阅读 0赞

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

##### 题目：旋转数组的最小数字 #####

*  LeetCode地址：[剑指 Offer 11. 旋转数组的最小数字][Offer 11.]
 *  描述：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 \[3, 4, 5, 1, 2\] 为 \[1, 2, 3, 4, 5\] 的一个旋转，该数组的最小值为1。
 *  示例：
    
        输入：[3,4,5,1,2]
        输出：1
        
        输入：[2,2,2,0,1]
        输出：0

##### 题解： #####

###### 方法一：从后往前暴力匹配： ######

*  思路：创建`temp`指针，只要发现 `numbers[temp] >= numbers[temp - 1]`，就前移指针，直到比它前一位小时停止，此时temp指向的就是最小值
 *  代码：
    
        public int minArray(int[] numbers) {
              
            //temp指针默认指向最后一位
            int temp = numbers.length - 1;
            while (temp > 0 && numbers[temp] >= numbers[temp - 1])
                //指针前移
                temp--;
            return numbers[temp];
        }
 *  复杂度分析：
    
     *  时间复杂度：O(n) 。
     *  空间复杂度：O(1)。
 *  测试：
    
    ![image-20201105165859536][]

###### 方法二：二分查找 + 暴力匹配 ######

*  思路：
    
    1.  根据题意，旋转数组数组内部有两个升序的序列，一个在前，一个在后。
    2.  值没有重复的情况下，根据 中值 与 右值 大小的比较，我们依然可以缩小匹配的范围，即可以用二分查找，具体步骤看代码：
 *  代码：
    
        public int minArray(int[] numbers) {
              
            int left = 0;
            int right = numbers.length - 1;
            int mid;
            while (left < right) {
              
                mid = left + (right - left) / 2;
                if (numbers[mid] > numbers[right]) {
              
                    //最小值一定在右侧，且一定不是mid，所以 left = mid + 1
                    left = mid + 1;
                }else if (numbers[mid] < numbers[right]) {
              
                    //最小值一定在左侧，但不确定mid是不是最小值，所以 right = mid
                    right = mid;
                }else {
              
                    //不能确定在左侧还是右侧，暴力缩小范围
                    right--;
                }
            }
            return numbers[left];
        }
 *  复杂度分析：
    
     *  时间复杂度：
        
        最差：O(n) 。数组所有元素相等，不能利用折半缩小范围，只能暴力匹配
        
        最好：O(logN) 。数组没有重复元素，每次都折半缩小范围。
     *  空间复杂度：O(1) 。
 *  测试：
    
    ![image-20201105165036015][]

##### 总结： #####

在大量数据的情况下，显然第二种方法要比第一种效率高很多！

[Offer 11.]: https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/
[image-20201105165859536]: https://gitee.com/yuziyan/cloudimage/raw/master/img/20201105165859.png
[image-20201105165036015]: https://gitee.com/yuziyan/cloudimage/raw/master/img/20201105165036.png