前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【力扣刷题】33. 搜索旋转排序数组

【力扣刷题】33. 搜索旋转排序数组

作者头像
jayjay
发布2022-11-02 16:55:35
2180
发布2022-11-02 16:55:35
举报
文章被收录于专栏:jay_blogjay_blog

一、题目描述

来源:力扣(LeetCode) 整数数组 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 。

示例 1:

代码语言:javascript
复制
输入:nums = [4,5,6,7,0,1,2], target = 0
输出:4

示例 2:

代码语言:javascript
复制
输入:nums = [4,5,6,7,0,1,2], target = 3
输出:-1

示例 3:

代码语言:javascript
复制
输入:nums = [1], target = 0
输出:-1

提示:

  • 1 <= nums.length <= 5000
  • -10^4 <= nums[i] <= 10^4
  • nums 中的每个值都 独一无二
  • 题目数据保证 nums 在预先未知的某个下标上进行了旋转
  • -10^4 <= target <= 10^4

二、思路分析

由于题目要求时间复杂度为 O(log n),故实现为二分法查找,怎么分是关键。

由于题目说数字了无重复,举个例子:

1 2 3 4 5 6 7 可以大致分为两类:

第一类 2 3 4 5 6 7 1 这种,也就是 nums[left] <= nums[mid]。此例子中就是 2 <= 5。

  • 这种情况下,前半部分有序。因此如果 nums[left] <=target<nums[mid],则在前半部分找,否则去后半部分找。

第二类 6 7 1 2 3 4 5 这种,也就是 nums[right] > nums[mid]。此例子中就是 6 > 2。

  • 这种情况下,后半部分有序。因此如果 nums[mid] <target<=nums[right],则在后半部分找,否则去前半部分找。

三、代码实现

代码语言:javascript
复制
class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            //中间点
            int mid = left + (right - left) / 2;
            if(nums[mid] == target){
                return mid;
            }else if(nums[left] <= nums[mid]){
                //左边连续递增
                if(target >= nums[left] &amp;&amp; target < nums[mid] ){
                    right = mid -1;
                }else{
                    left = mid + 1;
                }
            }else{
                //右边连续递增
                if(target > nums[mid]  &amp;&amp; target <= nums[right]){
                    left = mid +1;
                }else{
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}

四、运行结果

image.png
image.png

总结

这道题如果不是限制时间复杂度为 O(log n),用遍历也是可以解决的,不过时间复杂度为 O(n)了,不符合要求。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022-03-31,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、题目描述
  • 二、思路分析
  • 三、代码实现
  • 四、运行结果
  • 总结
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档