Java旋转数组中的最小数字(图文详解版)

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

目录

1.题目描述

2.题解

分析

具体实现

方法一(遍历):

方法二(排序):

方法三(二分查找):


1.题目描述

有一个长度为 n 的非降序数组,比如[1,2,3,4,5],将它进行旋转,即把一个数组最开始的若干个元素搬到数组的末尾,变成一个旋转数组,比如变成了[3,4,5,1,2],或者[4,5,1,2,3]这样的。请问,给定这样一个旋转数组,求数组中的最小值。

示例

输入:[3, 4, 5, 1, 2]

返回值:1

2.题解

分析

题目中的数组为

Java旋转数组中的最小数字(图文详解版),Java刷题,算法,数据结构,java

 题目要求我们找出其中的最小值

具体实现

方法一(遍历):

寻找数组中的最小值,遍历数组即可找到最小值

public class Solution {
    public int minNumberInRotateArray(int[] nums) {
        if(nums.length == 0){
            return -1;
        }
        int min = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (min > nums[i]) {
                min = nums[i];
            }
        }
        return min;
    }
}

 

方法二(排序):

使用Arrays.sort方法对数组进行降序排序,则nums[0]即为数组的最小值

import java.util.Arrays;

public class Solution {
    public int minNumberInRotateArray (int[] nums) {
        if(nums.length == 0){
            return -1;
        }
        Arrays.sort(nums);
        return nums[0];
    }
}

方法三(二分查找):

数组原本是一个升序数组,旋转之后,数组被分成两部分,前、后半部分分别为升序,后半部分小于前半部分,我们可以利用二分查找的思想,找到其旋转点,即可找到数组的最小值

首先找到数组首尾两端元素,并求出数组中间的下标

Java旋转数组中的最小数字(图文详解版),Java刷题,算法,数据结构,java

再将数组中间值与数组首尾两端元素进行比较,

nums[mid] > nums[right],则left = mid + 1

Java旋转数组中的最小数字(图文详解版),Java刷题,算法,数据结构,java 

 若nums[mid] < nums[right],则right = mid

Java旋转数组中的最小数字(图文详解版),Java刷题,算法,数据结构,java

nums[mid] = nums[right], 则将right向左移动一位,即right--

Java旋转数组中的最小数字(图文详解版),Java刷题,算法,数据结构,java

 然后进入下一次循环,循环的条件为left < right

通过不断缩小范围,最终能够找到数组的最小值

Java旋转数组中的最小数字(图文详解版),Java刷题,算法,数据结构,java

完整代码

public class Solution {
    public int minNumberInRotateArray(int[] nums) {
        if(nums.length == 0){
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            //找到数组的中点
            int mid = (left + right) / 2;
            if(nums[mid] > nums[right]){
                //旋转点在[mid+1, j]中,跳过mid+1左边元素
                left = mid + 1;
            } else if(nums[mid] < nums[right]){
                //旋转点在[left, mid]中,跳过mid右边元素
                right = mid;
            }else{
                //缩小right继续查找
                right--;
            }
        }
        //返回旋转点
        return nums[left];
    }
}

 :题目出自牛客网,链接如下

旋转数组的最小数字_牛客题霸_牛客网 (nowcoder.com)文章来源地址https://www.toymoban.com/news/detail-642706.html

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

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

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

相关文章

  • 剑指 Offer 11. && LeetCode 154. 旋转数组的最小数字

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

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

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

    2024年02月14日
    浏览(41)
  • 154. 寻找旋转排序数组中的最小值 II

    已知一个长度为  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], ...,

    2024年02月15日
    浏览(40)
  • HOT67-寻找旋转排序数组中的最小值

            leetcode原题链接 :寻找旋转排序数组中的最小值         上一篇 :HOT66-搜索旋转排序数组         下一篇: HOT68-寻找两个正序数组的中位数        已知一个长度为  n  的数组,预先按照升序排列,经由  1  到  n  次  旋转  后,得到输入数组。例如,原数组

    2024年02月16日
    浏览(48)
  • 每日一题 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], ...,

    2024年02月13日
    浏览(35)
  • Leetcode刷题详解——长度最小的子数组

    给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度**。**如果不存在符合条件的子数组,返回 0 。 示例 1: 示例 2: 示例 3: 提示: 1 = target = 109 1 = nums.length

    2024年02月07日
    浏览(49)
  • Golang每日一练(leetDay0052) 寻找旋转排序数组中的最小值I\II

    目录 153. 寻找旋转排序数组中的最小值 Find Minimum In Rotated Sorted Array  🌟🌟 154. 寻找旋转排序数组中的最小值 II Find Minimum In Rotated Sorted Array II  🌟🌟🌟 🌟 每日一练刷题专栏 🌟 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 已知一个长度为

    2024年02月16日
    浏览(38)
  • java数据结构与算法刷题-----LeetCode209. 长度最小的子数组

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 代码:时间复杂度O(n).空间复杂度O(1)

    2024年01月21日
    浏览(54)
  • leetcode刷题(轮转数组、买股票的最佳时机、买卖股票的最佳时机2、跳跃游戏、跳跃游戏2、最大子序列交替和、交替数字和、下降路径最小和)

    目录 1、轮转数组 2、买卖股票的最佳时机 3、买卖股票的最佳时机② 4、跳跃游戏 5、跳跃游戏2 6、最大子序列交替和 7、交替数字和 8、下降路径最小和 1、轮转数组 2、买卖股票的最佳时机 3、买卖股票的最佳时机② 4、跳跃游戏 5、跳跃游戏2 6、最大子序列交替和 7、交替数

    2024年02月16日
    浏览(32)
  • 长度最小的子数组(Java详解)

    目录 题目描述 题解 思路分析 暴力枚举代码 滑动窗口代码 给定一个含有  n   个正整数的数组和一个正整数  target  。 找出该数组中满足其和   ≥ target   的长度最小的  连续子数组   [numsl, numsl+1, ..., numsr-1, numsr]  ,并返回其长度 。 如果不存在符合条件的子数组,返回

    2024年02月05日
    浏览(35)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包