接口测试 GraphQL mysql安装 less 逻辑端口 model ios7 nosql 郑州网站开发 安卓项目实战 jq绑定click事件 jquery清除子元素 idea生成main方法 bentley软件介绍 docker查看所有容器 python调用函数 python安装环境变量 python字符串匹配 python的安装路径 javaswitch java初级教程 java对象和类 java正则替换 java的random java中collection java绝对值 linux系统教程 战地女记者 局域网助手 acmecadconverter 摩尔斯电码翻译器 华为交换机学习指南 fireworks8序列号 flash基础 go2lan php递归 软件龙头股 mtu设置多少最好 草图大师版本转换器 cdr字体变形
当前位置: 首页 > 学习教程  > python

【Leetcode】33. 搜索旋转排序数组(Search in Rotated Sorted Array)

2021/2/7 10:54:37 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

No33. 搜索旋转排序数组 题目 升序排列的整数数组 nums 在预先未知的某个点上进行了旋转(例如, [0,1,2,4,5,6,7] 经旋转后可能变为 [4,5,6,7,0,1,2] )。 请你在数组中搜索 target ,如果数组中存在这个目标值,则返回…

No33. 搜索旋转排序数组

题目

升序排列的整数数组 nums 在预先未知的某个点上进行了旋转(例如, [0,1,2,4,5,6,7] 经旋转后可能变为 [4,5,6,7,0,1,2] )。

请你在数组中搜索 target ,如果数组中存在这个目标值,则返回它的索引,否则返回 -1 。

示例 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 = [1], target = 0
  • 输出:-1

提示

提示:

  • 1 <= nums.length <= 5000
  • -10^4 <= nums[i] <= 10^4
  • nums 中的每个值都 独一无二
  • nums 肯定会在某个点上旋转
  • -10^4 <= target <= 10^4

解题代码(Python3)

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = nums[0]
        right = nums[-1]
        length = len(nums)
        if right < target < left:
            return -1
        elif target >= left:
            i = 0
            while i < length:
                if nums[i] > target:
                    return -1
                elif nums[i] == target:
                    return i
                i += 1
        else:
            i = length - 1
            while i >= 0:
                if nums[i] < target:
                    return -1
                elif nums[i] == target:
                    return i
                i -= 1
        return -1

思路:

因为左侧区域内的数一定是整体大于右侧区域内的,所以要先判断左右两端的值和target的关系:

  • 如果处于两值之间,那么说明不存在target
  • 如果大于等于left,要从左边开始向右遍历
  • 如果小于等于right,要从右边开始向左遍历

复杂度分析:

  • 时间复杂度O(n) 但比直接遍历节省时间
  • 空间复杂度O(1)

运行结果:

在这里插入图片描述


本文链接: http://www.dtmao.cc/news_show_2000237.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?