5

LeetCode: 154. Find Minimum in Rotated Sorted Array II

 3 years ago
source link: https://mozillazg.com/2021/04/leetcode-154-find-minimum-in-rotated-sorted-array-ii.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

题目

原题地址： https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,4,4,5,6,7] might become:

[4,5,6,7,0,1,4] if it was rotated 4 times.
[0,1,4,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums that may contain duplicates, return the minimum element of this array.

Example 1:

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

Example 2:

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

题目大意是，给一个旋转过的数组（这个数组旋转前是个有序数组，旋转操作会把数组元素按循环往后移。 比如，旋转一次就是把元素往后移动一次，结果就是原来的最后一个元素后移一位变成了第一个元素，其他元素也都后移了一位）， 找出这个数组中最小的那个元素，数组中的元素的值不是唯一的，可能有重复的值。

解法

这个题跟前面 153. Find Minimum in Rotated Sorted Array 基本是一样的，区别就是这里数组的元素的值不是唯一的。 因为数组中元素的值可能有重复的话，所以二分查找的时候不能每次缩短一半而是缩小一个元素的方式去查找

这个思路的 Python 代码类似下面这样：

class Solution:
    def findMin(self, nums):
        if len(nums) <= 2:
            return min(nums)

        left = 0
        right = len(nums) - 1
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] < nums[right]:
                right = mid
            # 虽然相等，但是不一定在左边还是右边，
            # 比如 [1, 2, 2] [3, 3, 1, 3]
            elif nums[mid] == nums[right]:
                right = right - 1
            else:
                left = mid + 1

        return nums[right]

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK