154 Find Minimum in Rotated Sorted Array II 尋找旋轉(zhuǎn)排序數(shù)組中的最小值 II
Description:
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:
Example 1:
Input: [1,3,5]
Output: 1
Example 2:
Input: [2,2,2,0,1]
Output: 0
Note:
This is a follow up problem to Find Minimum in Rotated Sorted Array.
Would allow duplicates affect the run-time complexity? How and why?
題目描述:
假設(shè)按照升序排序的數(shù)組在預(yù)先未知的某個(gè)點(diǎn)上進(jìn)行了旋轉(zhuǎn)辰斋。
( 例如，數(shù)組 [0,1,2,4,5,6,7] 可能變?yōu)?[4,5,6,7,0,1,2] )诞丽。
請找出其中最小的元素眉菱。
注意數(shù)組中可能存在重復(fù)的元素馋辈。
示例 :
示例 1：
輸入: [1,3,5]
輸出: 1
示例 2：
輸入: [2,2,2,0,1]
輸出: 0
說明：
這道題是 尋找旋轉(zhuǎn)排序數(shù)組中的最小值 的延伸題目。
允許重復(fù)會(huì)影響算法的時(shí)間復(fù)雜度嗎倍谜？會(huì)如何影響迈螟，為什么？
思路:
參考LeetCode #153 Find Minimum in Rotated Sorted Array 尋找旋轉(zhuǎn)排序數(shù)組中的最小值
- 逐個(gè)搜索
時(shí)間復(fù)雜度O(n), 空間復(fù)雜度O(1) - 二分法
當(dāng)nums[right] == nums[mid]時(shí), --right
其他的思路跟上一題一樣
時(shí)間復(fù)雜度O(n), 空間復(fù)雜度O(1), 平均時(shí)間復(fù)雜度O(lgn)
代碼:
C++:
class Solution
{
public:
int findMin(vector<int>& nums)
{
int left = 0, right = nums.size() - 1;
while (left < right)
{
int mid = left + ((right - left) >> 1);
if (nums[mid] > nums[right]) left = mid + 1;
else if (nums[mid] < nums[right]) right = mid;
else if (nums[mid] == nums[right]) --right;
}
return nums[left];
}
};
Java:
class Solution {
public int findMin(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + ((right - left) >>> 1);
if (nums[mid] > nums[right]) left = mid + 1;
else if (nums[mid] < nums[right]) right = mid;
else if (nums[mid] == nums[right]) --right;
}
return nums[left];
}
}
Python:
class Solution:
def findMin(self, nums: List[int]) -> int:
return min(nums)
