HOT67-寻找旋转排序数组中的最小值

这篇具有很好参考价值的文章主要介绍了HOT67-寻找旋转排序数组中的最小值。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

       leetcode原题链接:寻找旋转排序数组中的最小值

       上一篇:HOT66-搜索旋转排序数组

       下一篇:HOT68-寻找两个正序数组的中位数

题目描述

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

  • 若旋转 4 次,则可以得到 [4,5,6,7,0,1,2]
  • 若旋转 7 次,则可以得到 [0,1,2,4,5,6,7]

       注意,数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

       给你一个元素值 互不相同 的数组 nums ,它原来是一个升序排列的数组,并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

       你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1:

输入:nums = [3,4,5,1,2]
输出:1
解释:原数组为 [1,2,3,4,5] ,旋转 3 次得到输入数组。

示例 2:

输入:nums = [4,5,6,7,0,1,2]
输出:0
解释:原数组为 [0,1,2,4,5,6,7] ,旋转 4 次得到输入数组。

示例 3:

输入:nums = [11,13,15,17]
输出:11
解释:原数组为 [11,13,15,17] ,旋转 4 次得到输入数组。

提示:

  • n == nums.length
  • 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • nums 中的所有整数 互不相同
  • nums 原来是一个升序排序的数组,并进行了 1 至 n 次旋转

解题方法:二分查找。比较mid和right的大小关系,不断缩小求解空间。

1)如果nums[mid]小于nums[right],此时最小值为mid或者在mid左边,应该缩小求解区间,将right设置为mid;

2)如果nums[mid]大于或等于nums[right],说明当前mid在左段的升序空间,此时最小值一定在mid的右边;

【注意】循环执行的条件是left < right,循环结束后,left和right指向同一个元素,这个元素就是最小值。文章来源地址https://www.toymoban.com/news/detail-575029.html

C++代码

#include <iostream>
#include <vector> 

class Solution {
public:
    int findMin(std::vector<int>& nums) {
        int n = nums.size();
        int left = 0;
        int right = n - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] < nums[right]) { //比较中间值与右边值的大小关系
                right = mid; //right始终指向可能的最小值
            } else {
                left = mid + 1;
            }
        }
        return nums[right];
    }
};

到了这里,关于HOT67-寻找旋转排序数组中的最小值的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法Hot100系列】搜索旋转排序数组

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年01月21日
    浏览(55)
  • 《LeetCode 热题 HOT 100》——寻找两个正序数组的中位数

    本期给大家带来的是是《 LeetCode 热题 HOT 100 》第四题—— 寻找两个正序数组的中位数的 题目讲解 !!!() 本文目录 💥题意分析 💥解题思路: 1、直接法  (❌) 2、归并思想 (❌) ①《LeetCode》第88题——合并两个有序数组 3、二分查找(✔️) 整体思想: 题目如下

    2023年04月27日
    浏览(39)
  • 【算法训练-数组 五】【二分查找】:旋转排序数组的最小数字、旋转排序数组的指定数字

    废话不多说,喊一句号子鼓励自己:程序员永不失业,程序员走向架构!本篇Blog的主题是【数组的二分查找】,使用【数组】这个基本的数据结构来实现,这个高频题的站点是: CodeTop ,筛选条件为: 目标公司+最近一年+出现频率排序 ,由高到低的去 牛客TOP101 去找,只有两

    2024年02月09日
    浏览(50)
  • 剑指 Offer 11. && LeetCode 154. 旋转数组的最小数字

    参考资料:LeetCode 官方解答 剑指 Offer 11. 旋转数组的最小数字 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 给你一个可能存在 重复 元素值的数组 numbers ,它原来是一个升序排列的数组,并按上述情形进行了一次旋转。请返回旋转数组的最小元素

    2024年02月09日
    浏览(40)
  • leetcode 33.搜索旋转排序数组

    🌟 leetcode链接:搜索旋转排序数组 ps: 本题是二分查找的变形,旋转排序数组之后其实会 形成两个有序的区间 。算出平均下标先判断是否与 target 相等,因为这样可以减少代码的冗余。如果前者不成立则使用平均下标元素 midIndex 与 数组最后一个元素判断大小(因为我们可

    2024年02月13日
    浏览(45)
  • Leetcode-每日一题【剑指 Offer 11. 旋转数组的最小数字】

    把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 给你一个可能存在 重复 元素值的数组 numbers ,它原来是一个升序排列的数组,并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转,该数组的

    2024年02月14日
    浏览(39)
  • LeetCode 33题:搜索旋转排序数组

    目录 题目 思路 代码 暴力解法 分方向法 二分法 整数数组  nums  按升序排列,数组中的值  互不相同  。 在传递给函数之前, nums  在预先未知的某个下标  k ( 0 = k nums.length )上进行了  旋转 ,使数组变为  [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (下标 

    2024年02月13日
    浏览(42)
  • LeetCode - #81 搜索旋转排序数组 II

    我们社区陆续会将顾毅( Netflix 增长黑客,《iOS 面试之道》作者,ACE 职业健身教练。 )的 Swift 算法题题解整理为文字版以方便大家学习与阅读。 LeetCode 算法到目前我们已经更新了 80 期,我们会保持更新时间和进度( 周一、周三、周五早上 9:00 发布 ),每期的内容不多,

    2024年02月10日
    浏览(38)
  • Java旋转数组中的最小数字(图文详解版)

    目录 1.题目描述 2.题解 分析 具体实现 方法一(遍历): 方法二(排序): 方法三(二分查找): 有一个长度为 n 的非降序数组,比如[1,2,3,4,5],将它进行旋转,即把一个数组最开始的若干个元素搬到数组的末尾,变成一个旋转数组,比如变成了[3,4,5,1,2],或者[4,5,1,2,3]这样

    2024年02月13日
    浏览(36)
  • 算法leetcode|81. 搜索旋转排序数组 II(rust重拳出击)

    已知存在一个按非降序排列的整数数组 nums ,数组中的值不必互不相同。 在传递给函数之前, nums 在预先未知的某个下标 k ( 0 = k nums.length )上进行了 旋转 ,使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (下标 从 0 开始 计数)。例如, [0,1,2,4,4,4,5,6,

    2024年02月07日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包