leetcode153. 寻找旋转排序数组中的最小值

Myth丶恋晨 2022-12-19 11:43 177阅读 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];
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，177人围观）

还没有评论，来说两句吧...

相关阅读

相关 153. 寻找旋转排序数组中的最小值

153. 寻找旋转排序数组中的最小值已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。例如，原数组 nums = \[0,1,

曾经终败给现在/ 2024年04月01日 17:10/ 0 赞/ 76 阅读

相关 153. 寻找旋转排序数组中的最小值

算法描述： > 已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。 > 例如，原数组 nums =\[0,1,2,4,5,6,7

小咪咪/ 2024年04月01日 10:42/ 0 赞/ 109 阅读

相关 leetcode 153 寻找旋转排序数组中的最小值

已知一个长度为 `n` 的数组，预先按照升序排列，经由 `1` 到 `n` 次旋转后，得到输入数组。例如，原数组 `nums = [0,1,2,4,5,6,7]` 在变化后

待我称王封你为后i/ 2024年02月18日 09:25/ 0 赞/ 49 阅读

相关 153. 寻找旋转排序数组中的最小值

题目描述： > 已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。例如，原数组 nums = \[0,1,2,4,5,6,7\]

╰+哭是因爲堅強的太久メ/ 2023年10月11日 17:12/ 0 赞/ 31 阅读

相关 leetcode153. 寻找旋转排序数组中的最小值

题目描述: 假设按照升序排序的数组在预先未知的某个点上进行了旋转。例如，数组 \[0,1,2,4,5,6,7\] 可能变为 \[4,5,6,7,0,1,2\] 。请找出其

Myth丶恋晨/ 2022年12月19日 11:43/ 0 赞/ 178 阅读

相关 LeetCode153. 寻找旋转排序数组中的最小值【二分查找】

难度：`中等` 题目描述： > 已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。 > 例如，原数组 nums =\[0,1,

电玩女神/ 2022年11月17日 03:50/ 0 赞/ 189 阅读

相关 153. 寻找旋转排序数组中的最小值

> 已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。例如，原数组 nums = \[0,1,2,4,5,6,7\] 在变化后可能得到

旧城等待，/ 2022年10月08日 11:19/ 0 赞/ 212 阅读

相关 Leetcode 153. 寻找旋转排序数组中的最小值

题目重述已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。例如，原数组 nums = \[0,1,2,4,5,6,7\] 在变

偏执的太偏执、/ 2022年09月08日 05:58/ 0 赞/ 226 阅读

相关 153. 寻找旋转排序数组中的最小值

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。例如，原数组 nums = \[0,1,2,4,5,6,7\] 在变化后可能得到：

迈不过友情╰/ 2022年08月31日 07:18/ 0 赞/ 199 阅读

相关【LeetCode】153. 寻找旋转排序数组中的最小值

题目链接：[https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/description/

爱被打了一巴掌/ 2022年05月08日 05:46/ 0 赞/ 218 阅读