153 Find Minimum in Rotated Sorted Array 尋找旋轉(zhuǎn)排序數(shù)組中的最小值
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.
You may assume no duplicate exists in the array.
Example:
Example 1:
Input: [3,4,5,1,2]
Output: 1
Example 2:
Input: [4,5,6,7,0,1,2]
Output: 0
題目描述:
假設(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] )。
請(qǐng)找出其中最小的元素澎语。
你可以假設(shè)數(shù)組中不存在重復(fù)元素熊户。
示例 :
示例 1:
輸入: [3,4,5,1,2]
輸出: 1
示例 2:
輸入: [4,5,6,7,0,1,2]
輸出: 0
思路:
- 可以逐個(gè)搜索最小值
搜索到第一次增加的下標(biāo), 后一個(gè)即為最小值
時(shí)間復(fù)雜度O(n), 空間復(fù)雜度O(1) - 由于旋轉(zhuǎn)數(shù)組本身部分有序考慮用二分法
由于是查找最小值, 所以, 偏向于在左邊查找
中間與右邊界比較, 如果小于右邊界 right = mid
否則, left = mid + 1(這里 + 1是因?yàn)?mid比 right大說明一定不是 mid)
時(shí)間復(fù)雜度O(lgn), 空間復(fù)雜度O(1)
代碼:
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]) right = mid;
else left = mid + 1;
}
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]) right = mid;
else left = mid + 1;
}
return nums[left];
}
}
Python:
class Solution:
def findMin(self, nums: List[int]) -> int:
return min(nums)
