郑州 做网站,开发系统定制,微信公众号制作网页,wordpress 文章 nofollow题目链接 Leetcode.33 搜索旋转排序数组 mid 题目描述
整数数组 n u m s nums nums 按升序排列#xff0c;数组中的值 互不相同 。
在传递给函数之前#xff0c; n u m s nums nums 在预先未知的某个下标 k #xff08; 0 ≤ k n u m s . l e n g t h #xff09;…题目链接 Leetcode.33 搜索旋转排序数组 mid 题目描述
整数数组 n u m s nums nums 按升序排列数组中的值 互不相同 。
在传递给函数之前 n u m s nums nums 在预先未知的某个下标 k 0 ≤ k n u m s . l e n g t h k0 \leq k nums.length k0≤knums.length上进行了 旋转使数组变为 [ n u m s [ k ] , n u m s [ k 1 ] , . . . , n u m s [ n − 1 ] , n u m s [ 0 ] , n u m s [ 1 ] , . . . , n u m s [ k − 1 ] ] [nums[k], nums[k1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] [nums[k],nums[k1],...,nums[n−1],nums[0],nums[1],...,nums[k−1]]下标 从 0 0 0 开始 计数。例如 [ 0 , 1 , 2 , 4 , 5 , 6 , 7 ] [0,1,2,4,5,6,7] [0,1,2,4,5,6,7] 在下标 3 3 3 处经旋转后可能变为 [ 4 , 5 , 6 , 7 , 0 , 1 , 2 ] [4,5,6,7,0,1,2] [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 n u m s nums nums 和一个整数 t t t 如果 n u m s nums nums 中存在这个目标值 t t t则返回它的下标否则返回 − 1 -1 −1 。
你必须设计一个时间复杂度为 O ( l o g n ) O(log n) O(logn) 的算法解决此问题。
示例 1 输入nums [4,5,6,7,0,1,2], target 0 输出4 示例 2 输入nums [4,5,6,7,0,1,2], target 3 输出-1 示例 3 输入nums [4,5,6,7,0,1,2], target 3 输出-1 提示 1 ≤ n u m s . l e n g t h ≤ 5000 1 \leq nums.length \leq 5000 1≤nums.length≤5000 − 1 0 4 ≤ n u m s [ i ] ≤ 1 0 4 -10^4 \leq nums[i] \leq 10^4 −104≤nums[i]≤104 n u m s nums nums 中的每个值都 独一无二题目数据保证 n u m s nums nums 在预先未知的某个下标上进行了旋转 − 1 0 4 ≤ t a r g e t ≤ 1 0 4 -10^4 \leq target \leq 10^4 −104≤target≤104
解法二分 n u m s nums nums 是一个排好序的数组将其 旋转 之后它仍然满足 两段性。
我们让 l 0 , r n − 1 , m i d ( l r ) / 2 l 0 , r n - 1 , mid (l r) / 2 l0,rn−1,mid(lr)/2。
1.如果此时 [ l , m i d ] [l,mid] [l,mid] 区间是是有序的
如果 t t t 在区间 [ l , m i d ] [l,mid] [l,mid] 的范围内也就是 n u m s [ l ] ≤ t ≤ n u m s [ m i d ] nums[l] \leq t \leq nums[mid] nums[l]≤t≤nums[mid]那么就可以缩减 r r r即 r m i d r mid rmid否则说明 t t t 不在这个区间内那么就可以收缩 l l l即 l m i d 1 l mid 1 lmid1
2.如果此时 [ m i d 1 , r ] [mid 1,r] [mid1,r] 区间是有序的
如果 t t t 在区间 [ m i d 1 , r ] [mid 1,r] [mid1,r] 的范围内也就是 n u m s [ m i d 1 ] ≤ t ≤ n u m s [ r ] nums[mid 1] \leq t \leq nums[r] nums[mid1]≤t≤nums[r]那么就可以缩减 l l l即 l m i d 1 l mid 1 lmid1否则说明 t t t 不在这个区间内那么就可以收缩 r r r即 r m i d r mid rmid
时间复杂度 O ( l o g n ) O(logn) O(logn)
C代码
class Solution {
public:int search(vectorint nums, int t) {int n nums.size();int l 0 , r n - 1;while(l r){int mid (l r) 1;//这里必须为 nums[l] nums[mid]//因为 mid 是下取整的//如果当 nums 中的元素只有两个是 例如 nums [3,1] , t 1//此时 nums[l] 和 nums[mid] 都是同一个元素 即 3//如果不这样做的话 就会不满足这个判断进入到 else 的逻辑中 此时就会得出一个错误的答案if(nums[l] nums[mid]){if(nums[l] t t nums[mid]) r mid;else l mid 1;}else{if(nums[mid] t t nums[r]) l mid 1;else r mid;}}return nums[l] t ? l : -1;}
};
