广宁网站建设,怎样开网上商城,修改wordpress文章发布页,故宫文创产品设计牛客题霸 [ 旋转数组的最小数字] C题解/答案
题目描述
把一个数组最开始的若干个元素搬到数组的末尾#xff0c;我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转#xff0c;输出旋转数组的最小元素。 NOTE#xff1a;给出的所有元素都大于0#xff0c;若数组…牛客题霸 [ 旋转数组的最小数字] C题解/答案
题目描述
把一个数组最开始的若干个元素搬到数组的末尾我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转输出旋转数组的最小元素。 NOTE给出的所有元素都大于0若数组大小为0请返回0。
题解
两种方法 第一种很简单直接一遍循环找到最小值这种方法大家都会 我们介绍第二种二分 二分就像查字典一样,先翻最中间一页如果目标单词比我们所翻单词大说明目标单词在右边反之在左边假如在右边我们就进行一样的操作继续中间翻然后判断左右 二分答案就是用二分的方法在可能的答案区间里找出问题的答案大多数情况下用于求解满足某种条件下的最大小值前提是答案具有单调性同时也可以理解为是一种倒推方法先找答案在判断答案是否可行、有没有更优解。
代码
class Solution {
public:int minNumberInRotateArray(vectorint rotateArray) {int maxn1e9;for(int i0;irotateArray.size();i){maxnmin(maxn,rotateArray[i]);}return maxn;}
};二分法
class Solution {
public:int minNumberInRotateArray(vectorint rotateArray) {if(rotateArray.empty())return 0;int low 0;int hight rotateArray.size() - 1;int mid 0;while(low hight){mid low (hight - low)/2;if(rotateArray[mid] rotateArray[hight])low mid 1;elsehight mid;}return rotateArray[hight];}
};
