154. Find Minimum in Rotated Sorted Array II
假設一個長度為 n 的數組按升序排序後被旋轉了 1 到 n 次。例如，數組 nums = [0,1,4,4,5,6,7] 可能變成：[4,5,6,7,0,1,4] 如果它被旋轉了 4 次。
[0,1,4,4,5,6,7] 如果它被旋轉了 7 次。
注意，將數組 [a[0], a[1], a[2], ..., a[n-1]] 旋轉 1 次會得到數組 [a[n-1], a[0], a[1], a[2], ..., a[n-2]]。
給定可能包含重複元素的已排序旋轉數組 nums，返回此數組的最小元素。
你必須儘可能減少整體操作步驟。
範例 ：
輸入: nums = [1,3,5] 輸出: 1
Python
from typing import List
class Solution:
def findMin(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[mid] > nums[right]:
left = mid + 1
elif nums[mid] < nums[right]:
right = mid
else:
right -= 1 # Decrement right when nums[mid] == nums[right] to handle duplicates
return nums[left]
17.00MB, 50ms
C++
#include <vector>
using namespace std;
class Solution {
public:
int findMin(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1;
} else if (nums[mid] < nums[right]) {
right = mid;
} else {
// Handle duplicates by decrementing right
right--;
}
}
return nums[left];
}
};
14.62MB, 6ms
Javascript
/**
* @param {number[]} nums
* @return {number}
*/
var findMin = function(nums) {
let left = 0;
let right = nums.length - 1;
while (left < right) {
let mid = Math.floor((left + right) / 2);
if (nums[mid] > nums[right]) {
left = mid + 1;
} else if (nums[mid] < nums[right]) {
right = mid;
} else {
// Handle duplicates by decrementing right
right--;
}
}
return nums[left];
};
49.05MB, 79ms
