【LeetCode】面试题11. 旋转数组的最小数字

标签：区间   相等   http   numbers   怎么   误区   返回值   序列   object   

题目:

思路:

关于旋转数组有各种变种问题：是否有重复元素、寻找最大值最小值、寻找旋转点下标(旋转点的值等于最小值)、查找给定元素。本题就是对有重复元素的旋转数组，寻找其最小值。
首先想到二分查找没问题，关键在于怎么通过判断middle元素的相对大小去逐渐缩小搜索区间。如下图所示(无重复元素)

• 循环二分，middle = (left + right) // 2(向下取整)为每次二分的中点，恒有left

  • 当num[middle]
  • 当num[middle] > num[right]，middle处于左边序列，旋转点一定在[middle+1, right]闭区间内，因此执行left = middle+1(middle肯定不是旋转点)
  • 当num[middle] = num[right]，无法判断middle处于哪边序列，执行right = right-1，证明该操作的正确性只需证明操作后旋转点仍然在[left, right]区间内即可
    • 若middle在右边序列，则[middle, right]区间内所有元素相等，执行right = right-1只会抛弃一个重复值，旋转点仍然在[left, right]区间
    • 若middle在左边序列，由于左边序列任一元素 >= 右边序列任一元素，因此可推出旋转点num[x]
    • 若num[x]
    • 若num[x] = num[right]，则左边序列所有元素相等，并且等于[left, middle]区间内的元素
      • 若right > x，执行right = right-1后，旋转点仍然在[left, right]区间
      • 若right = x，执行right = right-1后，旋转点不在区间内，但返回的num[0]仍然是最小值。因为之后的二分循环一直在执行right = middle，而区间[left, middle]内的元素值一定都等于旋转点的值也就是最小值

代码:

Python

class Solution(object):
    def minArray(self, numbers):
        """
        :type numbers: List[int]
        :rtype: int
        """
        left = 0
        right = len(numbers) - 1
        while left  numbers[right]:
                left = middle + 1
            elif numbers[middle] 

相关问题

【LeetCode】面试题11. 旋转数组的最小数字

标签：区间   相等   http   numbers   怎么   误区   返回值   序列   object   

原文地址：https://www.cnblogs.com/cling-cling/p/12935855.html