今天分享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]
相关文章: