C 语言每日一题——旋转数组的最小数字

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

 一、题目内容

C 语言每日一题——旋转数组的最小数字,c语言,数据结构,算法

 提供一下该OJ题的链接:旋转数组的最小数字_牛客题霸_牛客网 (nowcoder.com)

二、题目分析

通过示例1可知,我们写代码的目的是在数组中找到一个最大值,并且返回来

我们很容易的会想到创建一个变量:int min = 0; 然后遍历整个数组,依次比较把一个最小值用该变量接收;但是时间复杂度是O(n),空间复杂度是O(1),这很显然不符合题目时间复杂度O(logn)的要求。

通过O(logn),这个要求,我们由果索因,会想到之前我们经常打招呼的二分查找法,其时间复杂度符合O(logn);但是二分查找的前提是:需要数组的有序的;

我们如果对它进行排序的话,那最快的排序的时间复杂度至少是O(nlogn),显然我们要先排序是不可行的。

我们在仔细回阅问题的描述;发现这个旋转数组也有他的特殊之处:

1.该数组有两个子数组是有序的。且该数组的最小值一定在数组的前一个字数组升序边界;

2.该数组的最后一个元素很大概率不属于我们要找的元素;

于是我们得出了一个类似于二分法(也是用双指针),但不同于二分法什么时候折半区间的考虑

C 语言每日一题——旋转数组的最小数字,c语言,数据结构,算法

 根据对上图的理解:我们就可以知道,这题中的二分法,与之前用的二分法,差别就在于判断条件。

那有人会问,若下标mid所指向的值 = 下标right所指向的值,该怎么办?

right-1;缩小范围;。

三、完整代码

/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @param numsLen int nums数组长度
 * @return int整型
 */
int minNumberInRotateArray(int* nums, int numsLen ) 
{
    int lift  = 0;
    int right = numsLen-1;
     //4 5 6 7 8 9 1 2 3
     //8 9 1 2 3
     //8 9 1
     //1
     while(lift<right)
    {
         int mid   = (lift+right)/2;
    if(nums[mid]>nums[right])
    {
        //前边的一半区间可以抛弃;
        lift = mid+1;
    }
    else if(nums[mid]<nums[right])
    {
        //后别的一半区间可以抛弃(不包括mid);
        right = mid;
    }
    else
    {
        //往前面走一位;
        right -= 1;
    }
    }
    return nums[lift];
}

 文章来源地址https://www.toymoban.com/news/detail-804359.html

到了这里,关于C 语言每日一题——旋转数组的最小数字的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • C语言每日一题:5.至少是其他数字的两倍+两个数组的交集。

    第一题: 1.需要我们返回最大数值的下标,所以先循环遍历我们的这个数组记录一下最大的数值和下标位置。 2.使用qsort排序(总是存在唯一的最大整数) 3所以排序之后的数组的倒数第二个元素就是除了最后一个元素在数组中最大的。 4.只需要判断这个数的两倍是否小于等于

    2024年02月15日
    浏览(46)
  • 每日一题---OJ题: 旋转数组

    片头 嗨! 小伙伴们,咱们又见面啦,今天我们一起来学习一道OJ题---旋转数组 emmm,看上去好像没有那么难,我们一起来分析分析  比如: 数组里面有7个元素,分别为 1, 2, 3, 4, 5, 6, 7 , 现在我们将数组中的元素向右轮转3个位置 第一次轮转:将最后一个元素\\\"7\\\"放在第一个位置,后面的元素

    2024年04月12日
    浏览(26)
  • ( 数组) 209. 长度最小的子数组——【Leetcode每日一题】

    难度:中等 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。 示例 1: 输入:target = 7, nums = [2,3,1,2,4,3] 输出:2 解释:子数

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

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

    2024年02月09日
    浏览(50)
  • 【剑指 offer】旋转数组的最小数字

    ✨个人主页:bit me👇 ✨当前专栏:算法训练营👇 核心考点:数组理解,二分查找,临界条件 描述: 有一个长度为 n 的非降序数组,比如[1,2,3,4,5],将它进行旋转,即把一个数组最开始的若干个元素搬到数组的末尾,变成一个旋转数组,比如变成了[3,4,5,1,2],或者[4,5,1,2,3]这

    2023年04月20日
    浏览(52)
  • (排序) 剑指 Offer 45. 把数组排成最小的数 ——【Leetcode每日一题】

    难度:中等 输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。 示例 1: 输入: [10,2] 输出: “102” 示例 2: 输入: [3,30,34,5,9] 输出: “3033459” 提示 : 0 nums.length = 100 说明: 输出结果可能非常大,所以你需要返回一个字符串而不

    2024年02月10日
    浏览(50)
  • 剑指offer面试题8 旋转数组的最小数字

    分析 首先一定要记住只要看到排序数组的查找,思维一定要往二分法上靠,然后再思考清楚如何利用二分法。而如何利用二分法一定要仔细分析所给的数组的特点:递增数组且最开始的若干元素搬到数组的末尾,相当于该数组由俩个递增小数组构成,前面的数组元素肯定大于

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

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

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

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

    2024年02月09日
    浏览(40)
  • 【每日一题Day220】LC1439有序矩阵中的第 k 个最小数组和 | 堆

    再来做一下373,之前都没有试过用小顶堆求第K小的,有序这个条件对我而言是摆设了 查找和最小的 K 对数字【LC373】 给定两个以 升序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。 定义一对值 (u,v) ,其中第一个元素来自 nums1 ,第二个元素来自 nums2 。 请找到和最小的 k

    2024年02月10日
    浏览(38)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包