东莞平台网站建设设计公司,交互效果好的网站,上海2022进口博览会,互联网域名注册旋转数组找最小#xff0c;这次值可以重复 不妨假设你已经做了上一题#xff0c;题解
上一题的方法1肯定是用不了了#xff0c;因为不再能完全分成2个不同的部分
所以我们沿着方法2走
如果 n u m s [ r ] nums[r] nums[r]#xff0c;我们依然可以找右半边 …旋转数组找最小这次值可以重复 不妨假设你已经做了上一题题解
上一题的方法1肯定是用不了了因为不再能完全分成2个不同的部分
所以我们沿着方法2走
如果 n u m s [ r ] nums[r] nums[r]我们依然可以找右半边 如果 n u m s [ l ] n u m s [ m i d ] n u m s [ r ] nums[l] nums[mid] nums[r] nums[l]nums[mid]nums[r],那可以直接返回 n u m s [ l ] nums[l] nums[l] 只能是情况1不可能是情况2和3 现在只剩下 n u m s [ m i d ] ≤ n u m s [ r ] , n u m s [ m i d ] ≤ n u m s [ l ] nums[mid] \le nums[r], nums[mid] \le nums[l] nums[mid]≤nums[r],nums[mid]≤nums[l] [ 3 , 3 , 3 , 3 , 1 , 3 , 3 ] n u m s [ l ] n u m s [ m i d ] n u m s [ r ] 3 [3, 3, 3, 3, 1, 3, 3]\ nums[l] nums[mid] nums[r] 3 [3,3,3,3,1,3,3] nums[l]nums[mid]nums[r]3 [ 3 , 3 , 1 , 3 , 3 , 3 , 3 ] n u m s [ l ] n u m s [ m i d ] n u m s [ r ] 3 ; [3, 3, 1, 3, 3, 3, 3]\ nums[l] nums[mid] nums[r] 3; [3,3,1,3,3,3,3] nums[l]nums[mid]nums[r]3; 不能直接排除一半,只能从右往左
那为啥不能是从左往右呢考虑 [ 0 , 1 ] [0,1] [0,1] 因为总体是一个单调递增的感觉从左往右可能g了
class Solution {
public:int findMin(vectorint nums) {int l 0, r nums.size() - 1;while(l r){int mid l (r - l) / 2;if(nums[mid] nums[r]){l mid 1;}else if(nums[l] nums[mid]){return nums[l];}else{ // nums[l] nums[mid] nums[r]// [3, 3, 3, 3, 1, 3, 3] nums[l] nums[mid] nums[r] 3;// [3, 3, 1, 3, 3, 3, 3] nums[l] nums[mid] nums[r] 3;// cannot decide left or right--r;}}return nums[l];}
};
