IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> leetcode:33.搜索旋转排序数组 -> 正文阅读

[数据结构与算法]leetcode:33.搜索旋转排序数组

33.搜索旋转排序数组

来源:力扣(LeetCode)

链接: https://leetcode.cn/problems/search-in-rotated-sorted-array/

整数数组 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 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 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

解法

  • 遍历:直接遍历元素,看是否能够找到与target相等的元素,并返回下标;
  • 二分法:虽然不是有序,但是部分是有序的,针对有序数组查找元素一般是使用二分查找法;这里需要判断mid落在左边有序数组,还是右边有序数组;然后再去判断target是否落在left-mid的中间,或者mid-right的中间。如果不在,更新left和right;
    能够根据有序的那部分判断出 target 在不在这个部分:
    • 如果 [ l , m i d ] [l, mid] [l,mid] 是有序数组,且 target 的大小满足 [ n u m s [ l ] , n u m s [ m i d ] ] [nums[l], nums[mid]] [nums[l],nums[mid]],应该将搜索范围缩小至 [ l , m i d ] [l, mid] [l,mid],否则在 [ m i d + 1 , r ] [mid + 1, r] [mid+1,r] 中寻找
    • 如果 [ m i d , r ] [mid, r] [mid,r] 是有序数组,且 target 的大小满足 [ n u m s [ m i d ] , n u m s [ r ] ] [nums[mid], nums[r]] [nums[mid],nums[r]],则我们应该将搜索范围缩小至 [ m i d , r ] [mid, r] [mid,r],否则在 [ l , m i d ? 1 ] [l, mid-1] [l,mid?1] 中寻找

在这里插入图片描述

二分法的写法有很多种,注意退出条件,left right的更新方式;

代码实现

遍历法

python实现

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        n = len(nums)
        if len(nums) == 1:
            if nums[0] == target:
                return 0
            else:
                return -1

        for i in range(n):
            if nums[i] == target:
                return i
        return -1        

c++实现

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        if (n == 1) {
            return nums[0] == target ? 0 : -1;
        }
        for(int i=0; i<n; i++) {
            if (nums[i] == target)
                return i;
        }
        return -1;
    }
};

复杂度分析

  • 时间复杂度: O ( N ) O(N) O(N)
  • 空间复杂度: O ( 1 ) O(1) O(1)

二分法

python实现

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        n = len(nums)
        if n == 1:
            return 0 if nums[0] == target else -1
        
        left = 0
        right = n-1
        while left <= right:
            mid = left + (right-left) // 2
            if nums[mid] == target:
                return mid
            if nums[left] <= nums[mid]:  # left part
                if nums[left] <= target <= nums[mid]:
                    right = mid
                else:
                    left = mid + 1
            elif nums[left] > nums[mid]:  # right part
                if nums[mid] <= target <= nums[right]:
                    left = mid
                else:
                    right = mid - 1
        return -1

c++实现

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        if (n==1) {
            return nums[0] == target ? 0 : -1;
        }

        int left = 0;
        int right = n-1;
        while (left <= right) {
            int mid = left + (right-left)/2;
            if (nums[mid] == target)
                return mid;

            if (nums[left] <= nums[mid]) {  // left part 
                    if (nums[left] <= target && target <= nums[mid])
                        right = mid;
                    else
                        left = mid + 1;
                }

            else {  // right part
                    if (nums[mid] <= target && target <= nums[right])
                        left = mid;
                    else
                        right = mid-1;
                }
        }
        return -1;
    }
};

复杂度分析

  • 时间复杂度: O ( l o g N ) O(logN) O(logN)
  • 空间复杂度: O ( 1 ) O(1) O(1)

参考

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-08-19 19:31:09  更:2022-08-19 19:34:45 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/25 21:34:49-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码