【剑指 offer】旋转数组的最小数字

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

【剑指 offer】旋转数组的最小数字

✨个人主页:bit me👇
✨当前专栏:算法训练营👇

核心考点:数组理解,二分查找,临界条件

描述:

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

数据范围:

1 ≤ n ≤ 10000,数组中任意元素的值: 0 ≤ val ≤ 10000

要求:

  • 空间复杂度:O(1)
  • 时间复杂度:O(logn)

示例1:

输入:[3,4,5,1,2]
返回值:1

示例2:

输入:[3,100,200,3]
返回值:3

思路:

  1. 第一种方法:此题就是寻找最小值,最容易普遍的一种思路就是直接遍历,因为是非递减的,所以最小值可能出现在任何一个地方,但是注意,旋转有种特性,旋转之后,有可能出现递减,那么引起递减的第一个数字肯定就是我们要找的最小值。
  2. 第二种方法:由于第一种方法效率比较低下,思路也不够新颖,在我们提到查找的时候,就该想到 " 查找的本质是排除 " 这句话。采用二分查找!因为是旋转非递减数组,所以可以把整个数组分为两半,mid 是中间二分的值,left 是最左边的值,right 是最右边的值,当我们的 mid 值大于 left 值的时候,就说明 mid 处于原始数组前半部分,根据非递减的特性,就说明目标最小值在 mid 的右侧,然后让 left = mid 之后继续进行二分查找,直到找到为止;反之,当我们的 mid 值小于 left 值的时候,就说明 mid 处于原始数组后半部分,根据非递减的特性,就说明目标最小值在 mid 的左侧,然后让 right = mid 之后继续进行二分查找,直到找到为止。
  • 注意非递减:所以有递增和相等两种可能,分别处理即可

第一种方法:

import java.util.ArrayList;
public class Solution {
	public int minNumberInRotateArray(int [] array) {
		if(array == null || array.length == 0){
			return 0;
		}
		for(int i = 0; i < array.length-1; i++){
			if(array[i] > array[i+1]){
				return array[i+1];
			}
		}
		return array[0];
	}
}

第二种方法:

  1. 先处理特殊情况,数组为空或者长度为 0 的时候
if(array == null || array.length == 0){
    return 0;
}
  1. 定义左右端点和中间值
int left = 0;
int right = array.length -1;
int mid = 0;
  1. 二分要循环进行查找,那么就要需要一个条件,条件就是 left < right
while(left < right){
	//...
}
  1. 后续代码在循环中完善,先考虑特殊情况,数组只有一个元素的时候
if(right - left == 1){
    mid = right;
    break;
}
  1. 非递减除了递增就还有左右端和中间值三个元素一样的情况
if(array[left] == array[right] && array[mid] == array[left]){
    int result = array[left];
    for(int i = left + 1; i < right; i++){
        if(result > array[i]){
            result = array[i];
        }
    }
    return result;
}

在这里我们就进行线性查找,依次遍历比较大小即可

  1. 中间值和左右端点进行比较直到找到为止
mid = (right + left) >> 1;
if(array[mid] >= array[left]){
    left = mid;
}else{
    right = mid;
}

总的代码:文章来源地址https://www.toymoban.com/news/detail-418973.html

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if(array == null || array.length == 0){
            return 0;
        }

        int left = 0;
        int right = array.length -1;
        int mid = 0;
        while(left < right){
            if(right - left == 1){
                mid = right;
                break;
            }
            //线性查找
            if(array[left] == array[right] && array[mid] == array[left]){
                int result = array[left];
                for(int i = left + 1; i < right; i++){
                    if(result > array[i]){
                        result = array[i];
                    }
                }
                return result;
            }
            mid = (right + left) >> 1;
            if(array[mid] >= array[left]){
                left = mid;
            }else{
                right = mid;
            }
        }
        return array[mid];
    }
}

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

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

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

相关文章

  • 【剑指offer】数组中重复的数字

    👑专栏内容:力扣刷题 ⛪个人主页:子夜的星的主页 💕座右铭:前路未远,步履不停 剑指offer:数组中重复的数字 在一个长度为 n 的数组里的所有数字都在 0 0 0 到 n − 1 n-1 n − 1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复,也不知道每个数字重复了几

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

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

    2024年02月10日
    浏览(49)
  • 剑指offer03.数组中重复的数字

    看到这道题的第一眼想到的是先给它排序,然后双指针从左往右遍历,写了一个冒泡排序,但是我想到了应该会超时,因为冒泡时间复杂度是n的平方,输入大小时10000,肯定会超时,然后右又看了一下题目看到数字都是0-n-1,灵感一下子就来了,我先创建一个等大的自然数数

    2024年02月11日
    浏览(39)
  • 剑指 Offer 03. 数组中重复的数字

    剑指 Offer 03. 数组中重复的数字 利用题目的限制条件: 所有数字都在 0~n-1 的范围内 通过交互让数字和下标一一对应,如果有多个数字对应同一个下标,那就找到了答案。 另一种写法

    2024年02月11日
    浏览(36)
  • 【剑指offer|1.数组中重复的数字】

    : 长度为n的数组nums中所有数字都在0~n-1范围内 返回任意一个重复的数字 总体时间复杂度和空间复杂度分析: 修改数组的方法: 因为有n个元素,每一个元素都在0~(n-1)范围内,如果元素不重复的话, 对数组重排之后,下标和元素值之间应该是一一对应的关系 但是因为

    2023年04月22日
    浏览(38)
  • 剑指 Offer 45. !!把数组排成最小的数(使用比较器的定制排序;快速排序)

    剑指 Offer 45. 把数组排成最小的数 中等 662 相关企业 输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。 示例 1: 输入: [10,2] 输出: “102” 示例 2: 输入: [3,30,34,5,9] 输出: “3033459” 这道题在左程云算法课上讲过,但是这次

    2024年02月14日
    浏览(42)
  • 剑指 Offer 39.数组中出现次数超过一半的数字

    剑指 Offer 39.数组中出现次数超过一半的数字 给定一个大小为 n 的数组 nums ,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在多数元素。 示例 1: 输入:nums = [3,2,3] 输出:3 示例 2: 输入:n

    2024年01月21日
    浏览(38)
  • 剑指offer39.数组中出现次数超过一半的数字

    这个题非常简单,解法有很多种,我用的是HashMap记录每个元素出现的次数,只要次数大于数组长度的一半就返回。下面是我的代码: 题解还有一种更牛逼的解法,把数组排序,然后返回数组中间的那个数就行,因为如果这个数出现的次数大于数组长度的一半的话,排完序后

    2024年02月13日
    浏览(36)
  • 剑指 Offer 39. 数组中出现次数超过一半的数字

    🚀 作者简介:一名在后端领域学习,并渴望能够学有所成的追梦人。 🚁 个人主页:不 良 🔥 系列专栏:🛸剑指 Offer  🛹Linux 📕 学习格言:博观而约取,厚积而薄发 🌹 欢迎进来的小伙伴,如果小伙伴们在学习的过程中,发现有需要纠正的地方,烦请指正,希望能够与诸

    2024年02月07日
    浏览(41)
  • 剑指 Offer 56 - I. 数组中数字出现的次数

    理想的人物不仅要在物质需要的满足上,还要在精神旨趣的满足上得到表现。        —— 黑格尔 目录 方法1:排序+指针 方法2:异或整个数组 题目: 一个整型数组  nums  里除两个数字之外,其他数字都出现了 两次 。请写程序找出这两个 只出现一次的数字。 要求时间复

    2023年04月16日
    浏览(37)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包