江门论坛网站建设,wordpress 网易云音乐插件,支付网站开发,上海小程序开发定制#x1f451;专栏内容#xff1a;剑指offer⛪个人主页#xff1a;子夜的星的主页#x1f495;座右铭#xff1a;前路未远#xff0c;步履不停 目录一、题目描述1、题目2、示例示例1示例2二、题目分析1、暴力法2、二分法三、代码汇总1、暴力法2、二分法一、题目描述
1、题… 专栏内容剑指offer⛪个人主页子夜的星的主页座右铭前路未远步履不停 目录一、题目描述1、题目2、示例示例1示例2二、题目分析1、暴力法2、二分法三、代码汇总1、暴力法2、二分法一、题目描述
1、题目
剑指offer旋转数组的最小数字
有一个长度为 n 的非降序数组比如[1,2,3,4,5]将它进行旋转即把一个数组最开始的若干个元素搬到数组的末尾变成一个旋转数组比如变成了[3,4,5,1,2]或者[4,5,1,2,3]这样的。请问给定这样一个旋转数组求数组中的最小值。 2、示例
示例1
输入[3,4,5,1,2]
输出1
示例2
输入[3,100,200,3]
输出3
二、题目分析
1、暴力法
旋转数组的原数组是一个非降序数组也就是说原数组中的元素是按照从小到大的顺序排列的。当将一个非降序数组旋转后我们可以把旋转数组分为两部分一部分是最大的一段非降序子数组另一部分是最小的一段非降序子数组。旋转数组的最小元素就在这两部分之间。比如数组[3, 4, 5,1,2] 它的最大的一段非降序子数组是[3,4,5]最小的一段非降序子数组是[1,2] 而最小元素就是最小的非降序子数组的第一个数。
所以说非降序数组在旋转之后有一个特征就是在遍历的时候原始数组是非递减的旋转之后就有可能出现递减而引起递减的数字就是最小值。
class Solution {
public:int minArray(vectorint numbers) {int n numbers.size(); //1int min numbers[0]; //2for(int i 1;in;i) //3{if(numbers[i] numbers[i-1]) //4{min numbers[i];break; //5}}return min;}
};1获取旋转数组的长度
2让旋转数组中第一个元素为最小值
3从第二个元素开始遍历旋转数组
4如果当前元素比前一个元素小证明引出现了递减那么当前元素就是旋转数组的最小元素
5找到了最小元素跳出循环
2、二分法
我们要知道一件事暴力查找的过程本质是排除的过程但是暴力遍历一次只能排除一个效率过低。既然是查找我们就可以用二分查找法来缩减时间复杂度。
前面分析过旋转数组的最小值位于非降序子数组和旋转子数组的交界处。所以我们可以使用二分查找来查找旋转子数组的第一个元素也就是最小值。旋转数组的最小值一定在数组的旋转点左侧或者就是旋转点。因此在查找过程中我们需要缩小查找区间尽可能保留可能包含最小值的区间使用left和right指针确定查找区间缩小区间的方式是根据mid的值与right的值的大小关系进行判断。如果numbers[mid]numbers[right]说明最小值在mid的右侧将left指针移动到mid1的位置如果numbers[mid]numbers[right]说明最小值在mid的左侧或者就是mid将right指针移动到mid的位置如果numbers[mid] numbers[right]说明可能是一个旋转点也可能不是将right指针移动一位。 class Solution {
public:int minArray(vectorint numbers) {int n numbers.size();int left 0,right n-1;//二分查找while(leftright){int mid (left right)/2;if(numbers[mid]numbers[right])left mid 1;else if (numbers[mid]numbers[right])right mid;else right --;}return numbers[left];}
};三、代码汇总
1、暴力法
class Solution {
public:int minArray(vectorint numbers) {int n numbers.size(); int min numbers[0]; for(int i 1;in;i) {if(numbers[i] numbers[i-1]) {min numbers[i];break; }}return min;}
};2、二分法
class Solution {
public:int minArray(vectorint numbers) {int n numbers.size();int left 0,right n-1;//二分查找while(leftright){int mid (left right)/2;if(numbers[mid]numbers[right])left mid 1;else if (numbers[mid]numbers[right])right mid;else right --;}return numbers[left];}
};
