整数数组 nums 按升序排列,数组中的值 互不相同 。
在传递给函数之前,nums 在预先未知的某个下标 k(0 <= k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]](下标 从 0 开始 计数)。例如, [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ,如果 nums 中存在这个目标值 target ,则返回它的下标,否则返回 -1 。
示例:
输入:nums = [4,5,6,7,0,1,2], target = 0 输出:4
思路:
应该有序数组的查找,两个有序数组,一般用二分查找
难点在于在于k是未知的,不然在target所在的地方进行二分查找就行了
最笨的,暴力法On复杂度,肯定不对
有没有快速得到k的办法?要朝这个思路考虑
先根据中间数和起点数的大小关系判断mid实在左段还是右端
如34512 target是4
中间数是5>3,mid在左端
若45123,中间数1<3 ,mid在右端
接下来判断target在mid左右,再调整左右边界
34512 target在mid左边,调整右边界为mid -1
45123 target在mid左边,接着调整右边界,差不多是这样
复杂度:
时间复杂度:二分查找 O(logn)
空间复杂度:O(1)
代码:public int search(int[] nums, int target) { int l = 0, r = nums.length-1; while(l<=r){ int mid = l+((r-l)>>1); if(nums[mid] == target) return mid; //说明mid在左端 if(nums[0]<=nums[mid]){ if(target=nums[l]){ r =mid-1; }else l =mid+1; }else{ //mid在右端 if(target>nums[mid] && target<=nums[r]){ l =mid+1; }else r =mid-1; } } return -1; }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)