[剑指 Offer 第 2 版第 11 题] “旋转数组的最小数字”做题记录

第 11 题：旋转数组中的最小数字

传送门：AcWing：旋转数组的最小数字，牛客网 online judge 地址。

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

输入一个升序的数组的一个旋转，输出旋转数组的最小元素。

例如数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为 $1$ 。

数组可能包含重复项。

注意：数组内所含元素非负，若数组大小为0，请返回-1。

样例：

输入：nums=[2, 2, 2, 0, 1]

输出：0

思路1 ：这是典型的可以使用二分法解决的问题，应用二分法的模板。特别注意，数组可能包含重复项，因此中间项如果等于末尾项，例如：[1, 1, 1, 1, 1, 0, 1] ，不能砍掉一半，只能把末尾项排除掉。

Python 代码：

  class Solution:
        def findMin(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            size = len(nums)
            if size == 0:
                return -1
            l = 0
            r = size - 1
            while l < r:
                mid = l + (r - l) // 2

                if nums[mid] < nums[r]:
                    # mid 有可能是最小值
                    # [7,8,1,2,3]
                    r = mid
                elif nums[mid] > nums[r]:
                    # mid 肯定不是最小值
                    # [7,8,9,10,11,1,2,3]
                    l = mid + 1
                else:
                    # 都有可能，所以就把 r 排除了
                    # [1,1,1,1,1,0,1]
                    assert nums[mid] == nums[r]
                    r = r - 1
            return nums[l]

思路2 ：还可以使用“分治法”，“分治法”就不用在乎有没有重复项了。但是“分治法”无异于把整个数组都看一遍，时间复杂度为 $O(n)$ 。

Python 代码：

  class Solution:
        def findMin(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            size = len(nums)
            if size == 0:
                return -1
            if size == 1:
                return nums[0]
            return self.__findMin(nums, 0, size - 1)

        def __findMin(self, nums, left, right):
            if left == right:
                return nums[left]
            if left + 1 == right:
                return min(nums[left], nums[right])
            mid = left + (right - left) // 2
            return min(self.__findMin(nums, left, mid), self.__findMin(nums, mid + 1, right))

分析：可以使用二分查找的思想，因为最小的数字很可能出现在首位，从后向前扫描是求解这道题的重要技巧，否则需要分类讨论，就变得麻烦了（即让后面的指针向前移动）。

Java 代码：

  public class Solution {

        // 虽然可以通过，但是 O(n) 的复杂度并不理想
        public int minNumberInRotateArray(int[] array) {
            // {3,4,5,1,2}
            // 1 2 3 4 5
            int len = array.length;
            for (int i = 1; i < len - 1; i++) {
                if (array[i] < array[i - 1]) {
                    return array[i];
                }
            }
            // 如果走到这里，说明数组是升序的，直接返回第 0 号索引的元素就可以了
            return array[0];
        }

        public static void main(String[] args) {
            // int[] nums = new int[]{3, 4, 5, 1, 2};
            int[] nums = new int[]{1, 2, 3, 4, 5};
            Solution solution = new Solution();
            int minNumberInRotateArray = solution.minNumberInRotateArray(nums);
            System.out.println(minNumberInRotateArray);
        }
    }

Java 代码：

  public class Solution2 {

        public int minNumberInRotateArray(int[] array) {
            int len = array.length;
            if (len == 0) {
                return 0;
            }
            int first = 0;
            int last = len - 1;
            while (first < last) {
                int mid = first + (last - first) / 2;
                if (array[mid] > array[last]) {
                    first = mid + 1;
                } else if (array[mid] == array[last]) {
                    last = last - 1;
                } else {
                    last = mid;
                }
            }
            return array[first];
        }

        public static void main(String[] args) {
            // int[] nums = new int[]{3};
            // int[] nums = new int[]{3, 4, 5, 6, 7, 8, 9, 1, 2};
            // int[] nums = new int[]{1, 2, 3, 4, 5};
            int[] nums = new int[]{2, 2, 2, 1, 2};
            Solution2 solution2 = new Solution2();
            int minNumberInRotateArray = solution2.minNumberInRotateArray(nums);
            System.out.println(minNumberInRotateArray);
        }
    }