(二分查找) 11. 旋转数组的最小数字 ——【Leetcode每日一题】

news/2024/10/15 13:55:20/

❓剑指 Offer 11. 旋转数组的最小数字

难度:简单

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。

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

注意,数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]]

示例 1:

输入:numbers = [3,4,5,1,2]
输出:1

示例 2:

输入:numbers = [2,2,2,0,1]
输出:0

提示

  • n == numbers.length
  • 1 <= n <= 5000
  • -5000 <= numbers[i] <= 5000
  • numbers 原来是一个升序排序的数组,并进行了 1n 次旋转

注意:本题与 154. 寻找旋转排序数组中的最小值 II 相同。

💡思路:二分查找

将旋转数组对半分可以得到一个包含最小元素的新旋转数组,以及一个非递减排序的数组。新的旋转数组的长度是原数组的一半,从而将问题规模减少了一半,这种折半性质的算法的时间复杂度为 O ( l o g 2 N ) O(log2N) O(log2N)
在这里插入图片描述
此时问题的关键在于确定对半分得到的两个数组哪一个是旋转数组,哪一个是非递减数组。我们很容易知道非递减数组的第一个元素一定小于等于最后一个元素。

通过修改二分查找算法进行求解(leftmidright 分别代表包含最小元素的新旋转数组 ):

  1. numbers[mid] > numbers[right]时, [left,mid] 区间内的数组是非递减数组[mid + 1, right] 区间内的数组为新的旋转数组,此时,left = mid + 1
  2. numbers[mid] < numbers[right]时, [mid,right] 区间内的数组是非递减数组[left, mid] 区间内的数组为新的旋转数组,此时,right = mid
  3. numbers[mid] = numbers[right]时, 无法判断哪一个是旋转数组,哪一个是非递减数组,此时 right- -,直到能判断。

🍁代码:(C++、Java)

C++

class Solution {
public:int minArray(vector<int>& numbers) {int left = 0;int right = numbers.size() - 1;if(right == 0) return numbers[0];while(left < right){int mid = left + (right - left) / 2;if(numbers[mid] > numbers[right]){left = mid + 1;}else if(numbers[mid] < numbers[right]){right = mid;}else{right--;}}return numbers[left];}
};

Java

class Solution {public int minArray(int[] numbers) {int left = 0;int right = numbers.length - 1;if(right == 0) return numbers[0];while(left < right){int mid = left + (right - left) / 2;if(numbers[mid] > numbers[right]){left = mid + 1;}else if(numbers[mid] < numbers[right]){right = mid;}else{right--;}}return numbers[left];}
}

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度 O ( l o g n ) O(logn) O(logn),平均时间复杂度为 O ( l o g ⁡ n ) O(log⁡n) O(logn),其中 n 是数组 numbers 的长度。如果数组是随机生成的,那么数组中包含相同元素的概率很低,在二分查找的过程中,大部分情况都会忽略一半的区间。而在最坏情况下,如果数组中的元素完全相同,那么 while 循环就需要执行 n 次,每次忽略区间的右端点,时间复杂度为 O(n)
  • 空间复杂度 O ( 1 ) O(1) O(1)

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!

注: 如有不足,欢迎指正!


http://www.ppmy.cn/news/1031568.html

相关文章

修改el-tooltip组件的背景色

修改el-tooltip组件的背景色 // 提示气泡的背景色 .el-tooltip__popper{background-color: pink !important; } .popper__arrow {border-top-color: pink !important; } .popper__arrow:after {border-top-color: pink !important; }

提升车间生产效率,这些做法很关键!

生产效率是制造生产企业的重要属性&#xff0c;对于影响生产效率的问题点&#xff0c;应当引起重视并规避&#xff0c;积极协调资源去改善&#xff0c;让企业能够有序、有章地运行。 一、影响生产效率的因素 1、产品加工工艺变更频繁 产品的加工工艺标准应在一段时间内不变…

JavaEE初阶:多线程 - 编程

1.认识线程 我们在之前认识了什么是多进程&#xff0c;今天我们来了解线程。 一个线程就是一个 "执行流". 每个线程之间都可以按照顺讯执行自己的代码. 多个线程之间 "同时" 执行 着多份代码. 引入进程这个概念&#xff0c;主要是为了解决并发编程这样的…

会员中心功能实现(小兔鲜儿)【Vue3】

会员中心 整体功能梳理和路由配置 整体功能梳理 个人中心 - 个人信息和猜你喜欢数据渲染我的订单 - 各种状态下的订单列表展示 路由配置(包括三级路由配置) 准备路由模版 <script setup> </script><template><div class"container">…

使用 Python 在 NLP 中进行文本预处理

一、说明 自然语言处理 &#xff08;NLP&#xff09; 是人工智能 &#xff08;AI&#xff09; 和计算语言学的一个子领域&#xff0c;专注于使计算机能够理解、解释和生成人类语言。它涉及计算机和自然语言之间的交互&#xff0c;允许机器以对人类有意义和有用的方式处理、分析…

“解引用“空指针一定会导致段错误吗?

可能有些朋友看见这个标题第一反应是嵌入式的某些内存中,0地址也是可以被正常访问的,所以对0地址的解引用不会发生错误,但我要说的情况不是这个,而是指一个真正的空指针,不仅是c/c中的0,(void*)0,NULL,还有nullptr,一个真正的空指针. 在c语言中,想获得某结构体的成员变量相对偏…

定长内存池设计ConcurrentMemoryPool

原理 还回来的内存用链表串联起来&#xff0c;称为自由链表 内存块自身进行链接&#xff0c;前四个字节存下一个的地址 结构 template<class T> class ObjectPool { public:T* New(){} private:char* _memory nullptr; //方便切割void* _freeList nullptr; };第一步…

.NET 6.0 重启 IIS 进程池

在 .NET 6.0 中&#xff0c;你可以使用 Microsoft.Web.Administration 命名空间提供的 API 来管理 IIS 进程池并实现重启操作。以下是一个示例代码&#xff0c;展示如何使用 .NET 6.0 中的 Microsoft.Web.Administration 来重启 IIS 进程池&#xff1a; using Microsoft.Web.A…