777fj做最好的网站,西安优化官网厂家,做网站经营流量,linux wordpress文章目录 前言题目解决方案一1.1 思路阐述1.2 源码 解决方案二2.1 思路阐述2.2 源码 总结 前言
查找算法的适用条件以及找到题目最核心的诉求是解决问题的关键。 题目
描述 有一个长度为 n 的非降序数组#xff0c;比如[1,2,3,4,5]#xff0c;将它进行旋转#xff0c;即把… 文章目录 前言题目解决方案一1.1 思路阐述1.2 源码 解决方案二2.1 思路阐述2.2 源码 总结 前言
查找算法的适用条件以及找到题目最核心的诉求是解决问题的关键。 题目
描述 有一个长度为 n 的非降序数组比如[1,2,3,4,5]将它进行旋转即把一个数组最开始的若干个元素搬到数组的末尾变成一个旋转数组比如变成了[3,4,5,1,2]或者[4,5,1,2,3]这样的。请问给定这样一个旋转数组求数组中的最小值。
数据范围 1 ≤ n ≤ 10000 1≤n≤10000 1≤n≤10000数组中任意元素的值: 0 ≤ v a l ≤ 10000 0≤val≤10000 0≤val≤10000 要求空间复杂度 O ( 1 ) O(1) O(1)时间复杂度 O ( l o g n ) O(logn) O(logn) 示例1 输入 [ 3 , 4 , 5 , 1 , 2 ] [3,4,5,1,2] [3,4,5,1,2] 返回值 1 1 1
示例2 输入 [ 3 , 100 , 200 , 3 ] [3,100,200,3] [3,100,200,3] 返回值 3 3 3
解决方案一
1.1 思路阐述
题目说的旋转什么的都不看精简一下就是一个数组里面找最小值。
不考虑时间复杂度和空间复杂度的话一个for循环遍历搞定。
1.2 源码
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param nums int整型vector * return int整型*/int minNumberInRotateArray(vectorint nums) {int minnums[0];for (int i0; inums.size()-1; i) {if(nums[i]min){minnums[i];}}return min;}
};解决方案二
2.1 思路阐述
看题目给的时间复杂度和空间复杂度大概率就是一种分治的思想那就是二分查找。
题目的数列有一个特性AB两个子序列组成一个序列C现在变成了BA由于C序列是非递减序列所以其实B序列中任意一个数都大于A。
用二分法来做的步骤如下
step 1双指针指向旋转后数组的首尾作为区间端点。 step 2若是区间中点值大于区间右界值则最小的数字一定在中点右边。(这里和序列特性有关系 step 3若是区间中点值等于区间右界值则是不容易分辨最小数字在哪半个区间比如[1,1,1,0,1]应该逐个缩减右界。 step 4若是区间中点值小于区间右界值则最小的数字一定在中点左边。 step 5通过调整区间最后即可锁定最小值所在。
2.2 源码
class Solution {
public:int minNumberInRotateArray(vectorint nums) {int i0,mid,jnums.size()-1;while (ij) {midi(j-i)/2;if(nums[mid]nums[j]){imid1;}else if(nums[mid]nums[j]){j--;}else{jmid;}}return nums[i];}
};总结
遇到有序数列的一种查找如果对时间复杂度有要求要考虑二分查找。
