一、题目内容
提供一下该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;缩小范围;。文章来源:https://www.toymoban.com/news/detail-804359.html
三、完整代码
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @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
//1
while(lift<right)
{
int mid = (lift+right)/2;
if(nums[mid]>nums[right])
{
//前边的一半区间可以抛弃;
lift = mid+1;
}
else if(nums[mid]<nums[right])
{
//后别的一半区间可以抛弃(不包括mid);
right = mid;
}
else
{
//往前面走一位;
right -= 1;
}
}
return nums[lift];
}
文章来源地址https://www.toymoban.com/news/detail-804359.html
到了这里,关于C 语言每日一题——旋转数组的最小数字的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!