剑指offer | 面试题8：旋转数组的最小数字

千羽

发布于 2021-12-29 13:06:16

2230

发布于 2021-12-29 13:06:16

文章被收录于专栏：程序员千羽

死磕算法系列文章

“Leetcode : https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof
“GitHub : https://github.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_08_minArray/Solution.java

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

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

思路：利用二分法，找到数组的中间元素 mid。

如果中间元素 > 数组第一个元素，在 mid 右边搜索变化点。
如果中间元素 < 数组第一个元素，我们需要在 mid 左边搜索变化点。
当找到变化点时停止搜索，满足 nums[mid] > nums[mid + 1] （mid+1 是最小值）或 nums[mid - 1] > nums[mid]（ mid 是最小值）即可。

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

“排序数组的查找问题首先考虑使用 二分法 解决，其可将 遍历法 的 线性级别 时间复杂度降低至 对数级别 。

算法流程：

初始化： 声明 i, j双指针分别指向 nums 数组左右两端；
循环二分： 设 m = (i + j) / 2m=(i+j)/2 为每次二分的中点（ "/" 代表向下取整除法，因此恒有 i≤m*<*j ），可分为以下三种情况：
1. 当nums[m]> nums[j]时 : m一定在左排序数组中,即旋转点x一定在[m + 1,j]闭区间内,因此执行i=m+ 1;
2. 当nums[m] < nums[j]时 : m一定在右排序数组中，即旋转点x一定在[i, m]闭区间内，因此执行j= m;
3. 当nums[m] = nums[j]时 : 无法判断m在哪个排序数组中，即无法判断旋转点x在[i, m]还是[m+ 1,j]区间中。解决方案:执行j= j- 1缩小判断范围，

复杂度分析：

时间复杂度O(log2N) :在特例情况下(例如[1,1,1,1]) ，会退化到O(N)。
空间复杂度0(1) : i,j , m量使用常数大小的额外空间。

package com.nateshao.sword_offer.topic_08_minArray;

/**
 * @date Created by 邵桐杰 on 2021/11/18 21:41
 * @微信公众号 程序员千羽
 * @个人网站 www.nateshao.cn
 * @博客 https://nateshao.gitee.io
 * @GitHub https://github.com/nateshao
 * @Gitee https://gitee.com/nateshao
 * Description: 剑指 Offer 08. 旋转数组的最小数字
 */
public class Solution {
    public static void main(String[] args) {
        int[] arr = {3, 4, 5, 8, 2};
        int i = minArray(arr);
        System.out.println("i = " + i);
        int min = minInReversingList(arr);
        System.out.println("min = " + min);
        int min2 = minInReversingList2(arr);
        System.out.println("min1 = " + min2);
    }

    /**
     * 官方参考
     *
     * @param numbers
     * @return
     */
    public static int minArray(int[] numbers) {
        int i = 0, j = numbers.length - 1;
        while (i < j) {
            int mid = (i + j) / 2;
            if (numbers[mid] > numbers[j]) i = mid + 1;
            else if (numbers[mid] < numbers[j]) j = mid;
            else j--;
        }
        return numbers[i];
    }

    /**
     * 思路：利用二分法，找到数组的中间元素 mid。
     * 如果中间元素 > 数组第一个元素，在 mid 右边搜索变化点。
     * 如果中间元素 < 数组第一个元素，我们需要在 mid 左边
     * 搜索变化点。当找到变化点时停止搜索，满足 nums[mid] > nums[mid + 1]
     * （mid+1 是最小值）或 nums[mid - 1] > nums[mid]（ mid 是最小值）即可。
     * <p>
     * 解法一：二分查找（变化点），时间复杂度：O(log n)，空间复杂度：O(1)
     *
     * @param array
     * @return
     */
    public static int minInReversingList(int[] array) {
        if (array == null || array.length == 0) return -1;
        if (array.length == 1 || array[array.length - 1] > array[0]) return array[0];

        int left = 0;
        int right = array.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (array[mid] > array[mid + 1]) return array[mid + 1];
            if (array[mid - 1] > array[mid]) return array[mid];

            if (array[mid] > array[0]) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }

    /**
     * 解法二：二分查找（最左下标），时间复杂度：O(log n)，空间复杂度：O(1)
     *
     * @param nums
     * @return
     */
    public static int minInReversingList2(int[] nums) {
        if (nums == null || nums.length == 0) return -1;

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