题目

LeetCode.154.寻找旋转排序数组中的最小值 II（困难）

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：

若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]
若旋转 7 次，则可以得到 [0,1,4,4,5,6,7]

注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。

给你一个可能存在重复元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。
提示：

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

进阶：

这道题是寻找旋转排序数组中的最小值的延伸题目。
允许重复会影响算法的时间复杂度吗？会如何影响，为什么？

题解

通过模拟可知，多次旋转后得到还是跟一次旋转一样的效果。

旋转一次后，数组可以分为左右两个子数组nums1和nums2，其中：

nums1和nums2本身都有序。
nums1中所有元素 >= nums2中所有元素。
- nums1的首元素可能与nums2尾元素相等。

最小的数字是nums2的第一个元素。

二分查找的时候，只要知道nums[mid]是位于nums1还是nums2中，就知道下一步应该往哪去缩减寻找范围。

怎么知道nums[mid]是不是位于`nums1`？

nums[mid] > nums[0]时，nums[mid]一定位于nums1。

nums[mid]位于nums1，接下来往哪找最小的数？

最小的数字是nums2的第一个元素，接下来要往右找。

怎么知道nums[mid]是不是位于nums2？

nums[mid] < nums[0]时，nums[mid]一定位于nums2。

nums[mid]位于nums2，接下来往哪找最小的数？

最小的数字是nums2的第一个元素，接下来要往左找。

nums[mid]位于nums2，怎么知道nums[mid]是不是最小的数？

如果nums[mid]就是最小的数字，mid处于两个升序序列的分割位置，那么nums[mid]一定是比前一个数字要小的，判断nums[mid] < nums[mid - 1]即可。

nums[mid] == nums[0]时，接下来应该往哪找？

由于数组允许有重复数字，nums1的首元素可能与nums2尾元素相等，这里就有两种情况：

如果nums1的首元素与nums2尾元素相等，不确定nums[mid]是在nums1还是nums2中，只能线性缩减边界。
如果nums1的首元素与nums2尾元素不相等，说明nums[mid]在nums1中，最小元素在nums2中，要向右找。

边界处理

只有一个元素，最小的数就是元素本身
如果最后一个数字比第一个数字大，说明没有旋转，第一数字就是最小的了

class Solution {
    fun findMin(nums: IntArray): Int {
        // 只有一个元素，最小的数就是元素本身
        // 如果最后一个数字比第一个数字大，说明没有旋转，第一数字就是最小的了
        if (nums.size == 1 || nums[0] < nums[nums.size - 1]) {
            return nums[0]
        }
        var low = 0
        var high = nums.size - 1
        while (low <= high) {
            val mid = low + (high - low) / 2
            // 如果mid大于第一个数，从第一个数字到mid都是升序的，旋转的部分在右边，最小的数也就在右边，接下来要往右找
            if (nums[mid] > nums[0]) {
                low = mid + 1
            } else if (nums[mid] < nums[0]) { // mid比第一个数小，说明mid已处于旋转的部分，最小的数在左边
                // 如果mid就是最小的数字，mid处于两个升序序列的分割位置，那么mid一定是比前一个数字要小的
                if (nums[mid] < nums[mid - 1]) {
                    return nums[mid]
                } else { // 还没找到最小的，所以要往左边找
                    high = mid - 1
                }
            } else if (nums[mid] == nums[0]) { // mid与第一个数相等
                // 如果mid在前面的升序序列接下来就要往右找，在后面的序列就要往左找
                // 但是无法判断这一点，只能从一侧依次递减
                // 如 [1, 0, 1, 1, 1] 和 [1, 1, 1, 0, 1]
                if (nums[mid] != nums[high]) {
                    low = mid + 1
                } else {
                    high--
                }
            }
        }
        // 如果没找到，说明数组元素全部相等
        return nums[0]
    }
}

平均时间复杂度O(log n)，最坏情况下数组元素全部相同，需要线性扫描整个数组，时间复杂度O(n)。

空间复杂度O(1)。

题目

题解

怎么知道nums[mid]是不是位于nums1？