python - 在旋转排序数组中查找最小值的回收数组解决方案

Question

我正在研究一个困难但愚蠢的平分搜索问题并调试了几个小时。

Find Minimum in Rotated Sorted Array II

154. Find Minimum in Rotated Sorted Array II

Hard

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

Find the minimum element.

The array may contain duplicates.

Example 1:

Input: [1,3,5]
Output: 1

Example 2:

Input: [2,2,2,0,1]
Output: 0

Note:

• This is a follow up problem to Find Minimum in Rotated Sorted Array.
• Would allow duplicates affect the run-time complexity? How and why?

广泛接受的答案需要 O(n) 时间，

class SolutionK:
    def findMin(self, nums):
        lo, hi = 0, len(nums)-1
        while lo < hi:
            mid = (hi +lo) // 2
            if nums[mid] > nums[hi]:
                lo = mid + 1
            elif nums[mid] < nums[hi]:
                hi = mid 
            else:
                hi -= 1      
        return nums[lo] 
    # why not min(nums)  or brute force

我认为这个问题可以通过回收数组来解决。

因为有重复，我们可以找到最右边的最大值，那么max + 1就是最小值。

#the mid
lo = 0
hi = len(nums)
mid = (lo+hi) // 2
mid = mid % len(nums)

和终止条件

if nums[mid-1] <= nums[mid] > nums[mid+1]: return mid as the peak.

不幸的是，我无法设计递减条件。

你能给点提示吗？

Answer 1

您确实可以使用二分法。如果数组仅包含唯一数字并且已旋转，则最左边或最右边的值将相对于中间点乱序。即array[0] <= array[len(array) // 2] <= array[-1]将是假的。另一方面，如果出现以下情况，则此条件可能成立:

• 数组根本没有旋转，
• 或有重复项，例如 [1, 1, 1, 1, 2] => (rotate left 1) [1, 1, 1, 2, 1] .

因此我们可以分别检查条件的左右部分(分别为 array[0] 和 array[-1])，如果其中一个无效，则检查相应的子数组(分别为左右子数组) .如果两个条件都不无效，我们需要检查双方并进行比较。

下面是一个示例实现(它只使用min，其中涉及的元素少于三个，即也可以进行简单比较):

def minimum(array):
    if len(array) <= 2:
        return min(array)
    midpoint = len(array) // 2
    if array[0] > array[midpoint]:
        return minimum(array[:midpoint+1])
    elif array[midpoint] > array[-1]:
        return minimum(array[midpoint+1:])
    else:  # Possibly dealing with duplicates.
        return min(minimum(array[:midpoint]),
                   minimum(array[midpoint:]))

from collections import deque
from random import randint, choices

for test in range(1000):
    l = randint(10, 100)
    array = deque(sorted(choices(list(range(l // 2)), k=l)))
    array.rotate(randint(-len(array), len(array)))
    array = list(array)
    assert min(array) == minimum(array)