泾川县建设局网站,企业网站托管方案内容,wordpress yosat,163企业邮箱费用旋转数组找最小值 其中数组中的值唯一
你可以顺序遍历#xff0c;当然一般会让你用二分来搞
方法1
数组可以分成两部分#xff0c;左边是 ≥ n u m s [ 0 ] \ge nums[0] ≥nums[0], 右边是 n u m s [ 0 ] nums[0] nums[0] 换句话说就是找第一个 n u m s…旋转数组找最小值 其中数组中的值唯一
你可以顺序遍历当然一般会让你用二分来搞
方法1
数组可以分成两部分左边是 ≥ n u m s [ 0 ] \ge nums[0] ≥nums[0], 右边是 n u m s [ 0 ] nums[0] nums[0] 换句话说就是找第一个 n u m s [ 0 ] nums[0] nums[0]的元素
如果 n u m s [ 0 ] nums[0] nums[0]则往右边否则左边
不过也需要排除有序的情况
class Solution {
public:int findMin(vectorint nums) {if(nums[0] nums.back())return nums[0];int n nums.size();int l 0, r n - 1;while(l r){int mid l (r - l) / 2;if(nums[mid] nums[0])l mid 1;else r mid - 1;}return nums[r 1];}
};方法2
依然二分
如果 n u m s [ m i d ] n u m s [ r ] nums[mid]nums[r] nums[mid]nums[r]那最小值肯定在右半边 如果 n u m s [ m i d ] ≤ n u m s [ r ] nums[mid]\le nums[r] nums[mid]≤nums[r], 那 n u m s [ m i d ] nums[mid] nums[mid]也可能称为最小所以 r m i d r mid rmid而不是 r m i d − 1 rmid-1 rmid−1
与普通二分的区别就是退出条件要 l r lr lr而不是 l ≤ r l\le r l≤r,不然你别想出去了
class Solution {
public:int findMin(vectorint nums) {int n nums.size();int l 0, r n - 1;while(l r){int mid l (r - l) / 2;if(nums[mid] nums[r])l mid 1;else r mid;}return nums[r];}
};
