从零学算法154

这篇具有很好参考价值的文章主要介绍了从零学算法154。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

154.已知一个长度为 n 的数组,预先按照升序排列,经由 1 到 n 次 旋转 后,得到输入数组。例如,原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到:
若旋转 4 次,则可以得到 [4,5,6,7,0,1,4]
若旋转 7 次,则可以得到 [0,1,4,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 ,它原来是一个升序排列的数组,并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须尽可能减少整个过程的操作步骤。
示例 1:
输入:nums = [1,3,5]
输出:1
示例 2:
输入:nums = [2,2,2,0,1]
输出:0文章来源地址https://www.toymoban.com/news/detail-642959.html

  • 暴力解法就不过多赘述了,从头到尾遍历一遍看哪个值突然不是保持升序的,那他就是最小值,或者直接对数组排序然后取首个元素,没意义。
  • 他人解法:首先经过旋转后以最小值 x 为分界点会分为左右两个升序数组,并且 x 一定在右数组,且为起点,因为旋转就是把最小值转到右边去了(旋转 0 次可以视为只有右数组)。从左右两端 left,right 为区间进行查找,中点值 mid 的可能性有三种:
    • mid < right: 说明 mid 在右数组,所以 mid 可能为 x,所以直接排除区间 (mid,right],即 right 更新为 mid
    • mid > right: 说明 mid 在左数组,在左数组 mid 就不可能为 x 了,所以所以直接排除区间 [left,mid],即 更新 left 为 mid+1
    • mid = right: 此时由于数组元素可能重复比如 [2,2,2,0,2] 和 [2,0,2,2,2],此时无法确定 mid 在左右哪个数组,不能直接去掉一部分区间了。但是无论是哪种情况,right 肯定是没用了,因为就算 right 等于 x,那我 mid 也等于 x,所以就谨慎地只去掉 right,也就是 right = right - 1。
    • 当 mid = right 时。换个说法再解释一下:首先如果 x 小于 right 对应的值,那 right 去掉也就去掉了,x 仍然在 [left,right-1];其次就算 right 对应的就是 x,首先 mid <= left ,因为 mid=right=x,x 已经是最小值了,那最小值肯定小于等于 left 了,同时 left<=mid<right 是恒成立的(因为 mid 是 (left+right)/2),但是你这时候 mid=right=x,也就是说 left<=mid<x,mid < x 代表了 mid 在左数组(因为 x 是右数组起点),既然 mid 在左数组,那么根据左数组的升序特性 left<=mid 恒成立mid <= left 并且 mid >= left,那就只能说 mid 岂不是就等于 left,由于区间 [left,mid] 是升序的,那么 left - mid 的值都是相等的。在 right 对应 x 时减 1 后代表的其实就是正好把右数组全部抛弃了,剩下的左数组全等,且都等于 x,那么无论你怎么查找,最后剩下的值都等于我们最终要的 x。
  • 为什么 mid 不和 left 比较,因为二分的目的是为了判断 mid 处于左右的哪个数组。mid > left 时比如 [1,2,3,4,5] 和 [3,4,5,1,2] mid 分别在右数组和左数组,这就无法判断了。
  •   public int minArray(int[] nums) {
          int i = 0,j = nums.length - 1;
          while(i<j){
              int mid = (i + j)/2;
              if(nums[mid] > nums[j])i=mid+1;
              else if(nums[mid] < nums[j])j=mid;
              else j--;
          }
          return nums[i];
      }
    

到了这里,关于从零学算法154的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 从零学算法50

    50 .实现 pow(x, n) ,即计算 x 的整数 n 次幂函数(即,xn )。 示例 1: 输入:x = 2.00000, n = 10 输出:1024.00000 示例 2: 输入:x = 2.10000, n = 3 输出:9.26100 示例 3: 输入:x = 2.00000, n = -2 输出:0.25000 解释:2-2 = 1/22 = 1/4 = 0.25 还真没我想的那么简单,这题可以学一下快速幂,我就直

    2024年02月07日
    浏览(34)
  • 从零学算法295

    295 .中位数是有序整数列表中的中间值。如果列表的大小是偶数,则没有中间值,中位数是两个中间值的平均值。 例如 arr = [2,3,4] 的中位数是 3 。 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。 实现 MedianFinder 类: MedianFinder() 初始化 MedianFinder 对象。 void addNum(int num) 将数据流中的

    2024年02月09日
    浏览(36)
  • 从零学算法560

    560 . 和为 K 的子数组 给你一个整数数组 nums 和一个整数 k ,请你统计并返回 该数组中和为 k 的连续子数组的个数 。 示例 1: 输入:nums = [1,1,1], k = 2 输出:2 示例 2: 输入:nums = [1,2,3], k = 3 输出:2 比较容易想到的是暴力解法(我承认我想不到)。为了不遗漏的得到每个连续

    2024年02月15日
    浏览(33)
  • 从零学算法34

    34 .给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target,返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。 示例 1: 输入:nums = [5,7,7,8,8,10], target

    2024年02月13日
    浏览(38)
  • 从零学算法113

    113 .给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 叶子节点 是指没有子节点的节点。 示例 1: 输入:root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出:[[5,4,11,2],[5,8,4,5]] 示例 2: 输入:root = [1,2,3]

    2024年02月11日
    浏览(35)
  • 从零学算法

    1575.给你一个 互不相同 的整数数组,其中 locations[i] 表示第 i 个城市的位置。同时给你 start,finish 和 fuel 分别表示出发城市、目的地城市和你初始拥有的汽油总量 每一步中,如果你在城市 i ,你可以选择任意一个城市 j ,满足 j != i 且 0 = j locations.length ,并移动到城市 j 。从

    2024年02月06日
    浏览(25)
  • 从零学算法(LCR 180)

    文件组合 .待传输文件被切分成多个部分,按照原排列顺序,每部分文件编号均为一个 正整数(至少含有两个文件)。传输要求为:连续文件编号总和为接收方指定数字 target 的所有文件。请返回所有符合该要求的文件传输组合列表。 注意,返回时需遵循以下规则: 每种组合

    2024年02月07日
    浏览(33)
  • 从零学算法(剑指 Offer 45)

    输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。 示例 1: 输入: [10,2] 输出: “102” 示例 2: 输入: [3,30,34,5,9] 输出: “3033459” 我的原始人解法:直接冒泡排序,把最先应该拼接的那个数不断后移,然后拼接即可。关键就

    2024年02月10日
    浏览(39)
  • 从零学算法 (剑指 Offer 13)

    地上有一个m行n列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、下移动一格(不能移动到方格外),也不能进入行坐标和列坐标的数位之和大于k的格子。例如,当k为18时,机器人能够进入方格 [35, 37] ,因为3+5+3+

    2024年02月11日
    浏览(34)
  • 从零开始学习 Java:简单易懂的入门指南之查找算法及排序算法(二十)

    ​ 也叫做顺序查找 ​ 说明:顺序查找适合于存储结构为数组或者链表。 基本思想 :顺序查找也称为线形查找,属于无序查找算法。从数据结构线的一端开始,顺序扫描,依次将遍历到的结点与要查找的值相比较,若相等则表示查找成功;若遍历结束仍没有找到相同的,表

    2024年02月10日
    浏览(44)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包