leetcode153. 寻找旋转排序数组中的最小值 Myth丶恋晨 2022-12-19 11:43 109阅读 0赞 题目描述: 假设按照升序排序的数组在预先未知的某个点上进行了旋转。例如,数组 \[0,1,2,4,5,6,7\] 可能变为 \[4,5,6,7,0,1,2\] 。 请找出其中最小的元素。 示例 1: 输入:nums = \[3,4,5,1,2\] 输出:1 示例 2: 输入:nums = \[4,5,6,7,0,1,2\] 输出:0 示例 3: 输入:nums = \[1\] 输出:1 提示: 1 <= nums.length <= 5000 \-5000 <= nums\[i\] <= 5000 nums 中的所有整数都是 唯一 的 nums 原来是一个升序排序的数组,但在预先未知的某个点上进行了旋转 分析:该题目一眼看过去就是使用二分查找,只需要mid指向的值和low和high判断即可 nums\[mid\]>nums\[high\] low=mid+1; 否则 high=mid; 代码: class Solution { public: int findMin(vector<int>& nums) { //二分查找 int low=0,high=nums.size()-1,mid; while(low<=high){ mid=(low+high)/2; if(low==high) break; //此时已经找到最小的结点 if(nums[mid]>nums[high]) low=mid+1; else high=mid; } //此处为开始的逻辑判断 有些复杂 /*if(low<0 || low>nums.size()-1) return nums[high]; else if(high<0 || high>nums.size()-1) return nums[low]; else return min(nums[low],nums[high]);*/ return nums[mid]; } };
还没有评论,来说两句吧...