C语言每日一题之旋转数求最小值

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

hello,今天我们分享一道题目,是牛客网上的一道题

求旋转数组中的最小值https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba?tpId=13&tqId=23269&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

那我们先来看一下题目的意思,首先要读懂题目讲的是什么
C语言每日一题之旋转数求最小值,c语言,开发语言
题目说一个非降序数组,什么是非降序呢,像1 2 3 4 5这种升序 也可以是1 1 2 2 3 4这种,但是大家可不要误解认为他是非序,非序就是随机数这些。
这道题呢有两种解法,一种就是我们从前往后一个一个比较过去,先定义一个min=首项,然后比他小的就赋值给min,这种大家就会,那今天我们就讲一下用二分查找的思路来给大家写

二分查找呢就是一个有序数组中,我们想要找一个数的位置的时候 ,我们取中间的数来进行比较,比如有一个升序数组,我们取出中间数,和我们要取的值进行比较,如果大于中间数,说明这个数在这个中间数的后面,那我们取中间数后面的数一直到最后的数的中间数,在进行比较,经过我们这样找数的方式,可以快速的找到它的位置

那我们就可以用这样的思路来分析这道题

  1. 中间大于右边 [3, 4, 5, 1, 2],这种情况下,最小数一定在右边;则left = middle + 1
  2. 中间等于右边 [1, 0, 1, 1, 1], 这个是[0, 1, 1, 1, 1] 旋转过来的,这时候需要缩小范围 right–;,注意不能是
    left++,因为是非降序数组,所以要缩小右边范围,把较小值向右推,符合我们的判断规则。
  3. 中间小于右边 [5, 1, 2, 3, 4], 这种情况下,最小数字则在左半边;则right = middle
int minNumberInRotateArray(int* rotateArray, int rotateArrayLen ) {
if (rotateArrayLen == 0) return 0;
int left = 0, right = rotateArrayLen - 1, mid;
if (rotateArray[right] > rotateArray[left]) return rotateArray[0];
while(left < right) {
mid = left + (right - left) / 2;
if (rotateArray[mid] > rotateArray[right]) left=mid+1;
//中间的数大,那么我们就要往mid后面找,说明最小值在mid后面
//而且保证mid不是最小数,因为right有更小的数
else if (rotateArray[mid] == rotateArray[right]) right--;
//如果是这样的旋转数{0,1,1,1,1,1,1}
else right = mid;//中间的数小,那我们就要往右边找,而且这个中间数也可以是最小的数,所以不能写成right=mid-1
}
return rotateArray[left];//因为只有right=left的时候while循环条件不满足,那么才会退出循环,所以这里写right也对
}

今天的分享就到这,我们一起加油文章来源地址https://www.toymoban.com/news/detail-540682.html

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

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

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

相关文章

  • C语言每日一题之整数求二进制1的个数

    今天分享一道题目,用三种方法来求解 二进制1的个数 方法1 我们的十进制除10和取余数就可以得到我们每一位的数字,那我们的二进制也可 以 这是一种方法,另外一种就是我们可以用移位操作符来算 这个方法是不是也是特别妙呢,当然还有更妙的方法,请看!!! 相信看

    2024年02月15日
    浏览(58)
  • LeetCode每日一题之 复写0

    目录 题目介绍: 算法原理: 特殊位置处理: 代码实现: 题目链接:. - 力扣(LeetCode) 这种对数组元素进行修改,移动的题目我们仍然可以使用双指针法,不过我们按照常规思路从左到右处理数组,不难发现如下这种问题: 当cur指向1时,让dest下一个元素复写cur指向的元素

    2024年04月23日
    浏览(50)
  • 每日一题之判断子序列

    题目链接 给定字符串 s 和 t ,判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如, \\\"ace\\\" 是 \\\"abcde\\\" 的一个子序列,而 \\\"aec\\\" 不是)。 示例 1: 示例 2: 提示: 0 = s.length = 100 0 = t.le

    2024年02月16日
    浏览(40)
  • 每日一题之最长连续递增序列

    题目链接 给定一个未经排序的整数数组,找到最长且 连续递增的子序列 ,并返回该序列的长度。 连续递增的子序列 可以由两个下标 l 和 r ( l r )确定,如果对于每个 l = i r ,都有 nums[i] nums[i + 1] ,那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

    2024年02月12日
    浏览(37)
  • Python:每日一题之矩阵拼接

    问题描述 已知 3 个矩形的大小依次是 a1​×b1​,a2​×b2​ 和 a3​×b3​ 。 用这 3 个矩形能拼 出的所有多边形中, 边数最少可以是多少? 例如用 3×2 的矩形(用 A 表示)、 4×1 的矩形 (用 B 表示) 和 2×4 的矩 形(用 C 表示)可以拼出如下 4 边形。   例如用 3×2 的矩形 (用

    2024年02月11日
    浏览(36)
  • 每日一题之常见的排序算法

    排序是最常用的算法,常见的排序算法有冒泡排序、选择排序、插入排序、快速排序、希尔排序和归并排序。除此之外,还有桶排序、堆排序、基数排序和计数排序。 1、冒泡排序 冒泡排序就是把小的元素往前放或大的元素往后放,比较的是相邻的两个元素。 时间复杂度:

    2024年02月13日
    浏览(39)
  • 每日一题之打家劫舍

    题目链接 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统, 如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。 给定一个代表每个房屋存放金额的非负整数数组,计算

    2024年02月08日
    浏览(41)
  • 每日一题之数值的整数次方

    描述: 实现函数 double Power(double base, int exponent),求 base 的 exponent 次方。 注意: 1.保证base和exponent不同时为0。 2.不得使用库函数,同时不需要考虑大数问题 3.有特殊判题,不用考虑小数点后面0的位数。 我的思路:直接使用递归,让它每次乘一个它自身。但这存在一个问题,

    2024年02月12日
    浏览(37)
  • 每日一题之打家劫舍II

    题目链接 你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统, 如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报

    2024年02月08日
    浏览(40)
  • 每日一题之两个字符串的删除操作

    题目链接 给定两个单词  word1  和  word2  ,返回使得  word1  和   word2  ** 相同 所需的 最小步数 。 每步  可以删除任意一个字符串中的一个字符。 示例 1: 示例  2: 提示: 1 = word1.length, word2.length = 500 word1  和  word2  只包含小写英文字母 我们可以定义一个二维数组 dp ,

    2024年02月15日
    浏览(37)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包