LeetCode 热题 HOT 100Java题解之33. 搜索旋转排序数组(击败了100%的用户)

LeetCode 热题 HOT 100Java题解之33. 搜索旋转排序数组(击败了100%的用户),第1张

LeetCode 热题 HOT 100Java题解之33. 搜索旋转排序数组(击败了100%的用户) 题目:

整数数组 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;
    }

 

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5686878.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存