点击上方“专知”,关注获取专业AI知识”
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.
题目的意思是给定一个升序排列的数组,该数组在某一个点翻转了,根据翻转后的数组求该数组的最小值。
方法1:通过观察,翻转后的数组,如果某一个数比前一个数小,那么这个数就是数组的最小值,遍历该数组找到最小值,时间复杂度O(n).
class Solution {
public:
int findMin(vector<int>& nums) {
int re=nums[0];
for(int i=0; i<nums.size()-1; ++i)
{
if(nums[i]>nums[i+1])
re=nums[i+1];
}
return re;
}
};
方法2:二分查找法的变形。先判断区间是否是单调递增区间,也就是看l是否小于等于r,如果是的话,l就是所求。如果不是单调递增区间,也就是l比r大:如果mid大于等于l,说明最小值落在右半部分;如果mid比l小,说明最小值落在左半部分,也可能最小值就是mid本身。
class Solution {
public:
int findMin(vector<int>& nums) {
int l=0, r=nums.size()-1;
while(l<r && nums[l]>nums[r])
{
int mid=(l+r)/2;
if(nums[mid]>=nums[l])
l=mid+1;
else
r=mid;
}
return nums[l];
}
};
人生易老,唯有陪伴最长情,加油!
以上就是关关关于这道题的总结经验,希望大家能够理解,有什么问题可以在我们的专知公众号平台上交流或者加我们的QQ专知-人工智能交流群 426491390,也可以加入专知——Leetcode刷题交流群(请先加微信小助手weixinhao: Rancho_Fang)。