【leetcode刷题】T10-寻找旋转排序数组中的最小值II
【leetcode刷题】T10-寻找旋转排序数组中的最小值II
今天分享leetcode第10篇文章，也是leetcode第154题—Find Minimum in Rotated Sorted Array II（寻找旋转排序数组中的最小值II），地址是：https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/
【英文题目】（学习英语的同时，更能理解题意哟~）
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
【中文题目】
设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。
注意数组中可能存在重复的元素。
示例 1：
输入: [1,3,5]
输出: 1
示例 2：
输入: [2,2,2,0,1]
输出: 0
【思路】
本题与昨天分享的「寻找旋转排序数组中的最小值」基本类似，同样存在两种解法：一是暴力破解，循环遍历甚至直接使用min函数时间复杂度为O(n)；二是考虑使用类似二分查找的方法。本文主要介绍第二种思路。
昨天提到，当nums[0] < nums[length - 1]时，直接返回nums[0]作为最小值；否则使用二分查找，只要nums[mid] > nums[0]，则搜索右半区域，反之则搜索左半区域。
今天的题与昨天的唯一区别是，数组中可能存在重复元素。
当nums[0] == nums[length - 1]时，说明nums[0]这个值在数组中存在多个甚至整个数组都是这个值。同理当nums[l] == nums[r]时，数组l->r区间存在多个相同值（此时nums[l] != nums[0]才说明l->r区间是同一元素），那么我们可以移动某一个元素，再进行比较。
当nums[l] ！= nums[r]时，nums[mid] > nums[0]，搜索右半区域，反之则搜索左半区域。
有一点值得注意，当nums[mid] < nums[0]时，可能mid位置的元素为最小值，所以r只能移动到mid处，比如对于数组[3, 1, 2]。
【代码】
python版本
class Solution(object):
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
length = len(nums)
l, r = 0, length - 1
while l <= r:
# 小于，则nums[l]为最小值
if nums[l] < nums[r]:
break
# 元素相同，考虑下一元素的对比
if nums[l] == nums[r]:
r -= 1
continue
mid = (l + r) // 2
if nums[mid] >= nums[l]:
l = mid + 1
# 元素小，有可能nums[mid]是最小值
else:
r = mid
return nums[l]相关文章：