徐州建设工程交易网站,wordpress上传图片时发生了错误,php网站培训班,好的网站设计制作一、题目内容 提供一下该OJ题的链接#xff1a;旋转数组的最小数字_牛客题霸_牛客网 (nowcoder.com)
二、题目分析
通过示例1可知#xff0c;我们写代码的目的是在数组中找到一个最大值#xff0c;并且返回来#xff1b;
我们很容易的会想到创建一个变量#xff1a;int… 一、题目内容 提供一下该OJ题的链接旋转数组的最小数字_牛客题霸_牛客网 (nowcoder.com)
二、题目分析
通过示例1可知我们写代码的目的是在数组中找到一个最大值并且返回来
我们很容易的会想到创建一个变量int min 0; 然后遍历整个数组依次比较把一个最小值用该变量接收但是时间复杂度是O(n)空间复杂度是O(1),这很显然不符合题目时间复杂度O(logn)的要求。
通过O(logn)这个要求我们由果索因会想到之前我们经常打招呼的二分查找法其时间复杂度符合O(logn)但是二分查找的前提是需要数组的有序的
我们如果对它进行排序的话那最快的排序的时间复杂度至少是O(nlogn)显然我们要先排序是不可行的。
我们在仔细回阅问题的描述发现这个旋转数组也有他的特殊之处
1.该数组有两个子数组是有序的。且该数组的最小值一定在数组的前一个字数组升序边界
2.该数组的最后一个元素很大概率不属于我们要找的元素
于是我们得出了一个类似于二分法也是用双指针但不同于二分法什么时候折半区间的考虑 根据对上图的理解我们就可以知道这题中的二分法与之前用的二分法差别就在于判断条件。
那有人会问若下标mid所指向的值 下标right所指向的值该怎么办
right-1缩小范围。
三、完整代码
/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param nums int整型一维数组 * param numsLen int nums数组长度* return int整型*/
int minNumberInRotateArray(int* nums, int numsLen )
{int lift 0;int right numsLen-1;//4 5 6 7 8 9 1 2 3//8 9 1 2 3//8 9 1//1while(liftright){int mid (liftright)/2;if(nums[mid]nums[right]){//前边的一半区间可以抛弃lift mid1;}else if(nums[mid]nums[right]){//后别的一半区间可以抛弃(不包括mid)right mid;}else{//往前面走一位right - 1;}}return nums[lift];
}
