力扣刷题--数组--第二天

  今天仍然做二分查找相关的题目。先来回顾一下二分查找的方法和使用的条件。二分查找是在数组中查找目标值的一种方法,通过边界索引确定中间索引,判断中间索引处的元素值和目标值的大小,来不断缩小查找区间。使用二分查找有如下一些限制:

  • 数组是单调递增或单调递减;
  • target值唯一。

话不多说,直接上题!

1.题目链接

题目名称:在排序数组中查找元素的第一个和最后一个位置
题目详情:
  非减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
  如果数组中不存在目标值 target,返回 [-1, -1]。
  你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1:
输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]
示例 2:

输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]

示例 3:
输入:nums = [], target = 0
输出:[-1,-1]

解法一:我自己写出来的!明天奖励自己吃个鸡腿,哈哈哈哈
主要思路:
  首先题目中给定的数组是非减顺序,其实不符合二分查找的条件,但是题目最终是要找到等于target的开始位置和结束位置。这里可以分为三种情况:
  (1) target不在数组中,则和普通的二分查找方式一样;
  (2) target在数组中,但有且仅有一个,那也和普通的二分查找一样;
  (3) target在数组中,但个数不止一个,这种情况下当nums[mid] == target时,首先就可以把mid存储起来,其次因为在当前这个区间内不止一个target,所以不能按照以前的方式直接返回或确定当前mid左侧的值一定全部小于target,mid右侧的值一定全部大于target。故这里就会以mid为节点,分成两个子区间[lindex,mid-1]和[mid+1,rindex],两个子区间分别再进行二分查找,寻找满足条件的索引。

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
    	# 设定一个list,用来存储数组中等于target的索引
    	# 且out要么为空要么有且仅有两个元素,包括左边界和右边界
        out=[]  
        def run(lindex,rindex):
            if lindex > rindex:
                return -1
            mid=lindex+(rindex-lindex)//2
            # 当mid索引元素不等于target时,像之前普通二分查找法一样
            if nums[mid] != target:
                if nums[mid]>target:
                    rindex=mid-1
                else:
                    lindex=mid+1
                return run(lindex,rindex)
            # 当mid索引元素==target时
            else:
                if len(out) == 0:
                	# 若当前mid是第一个判断为target的索引,则填充至out
                    out.extend([mid,mid]) 
                else:
                	# 当满足条件的索引大于1个时,
                	# 则这里判断当前索引是左边界还是右边界
                    out[0]=min(out[0],mid)
                    out[1]=max(out[1],mid)
                # 当mid索引==target时,需将[lindex,rindex]划分成两个子区间
                # 分别进行二分查找,继续搜索==target的索引
                run(lindex,mid-1)
                run(mid+1,rindex)

        run(0,len(nums)-1)
        if len(out) == 0:
            return [-1,-1]
        return out

在这里插入图片描述

解法二:看的代码随想录的解法,可以学习这种思路
解题思路:
  这里使用两次二分法分别去查找target的左边界和右边界(特别注意的是,这里的左边界指的是第一个target索引的前面一位索引,右边界也是一样),也可以分为三种情况去讨论,分别是:
  (1) target小于数组的最小值或大于数组的最大值,即在数组范围的左侧或右侧;
  (2) target在数组范围内,但target不在数组中;
  (3) target在数组中。

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        # 获得右边界
        def  getRightBorder(nums,target):
            rightBorder=-2
            lindex=0
            rindex=len(nums)-1
            while lindex<=rindex:
                mid=lindex+(rindex-lindex)//2
                if nums[mid] > target:
                    rindex=mid-1
                else:
                    lindex=mid+1
                    rightBorder=lindex  # 这里右边界更新
            return rightBorder
        # 获得左边界
        def getLeftBorder(nums,target):
            leftBorder=-2
            lindex=0
            rindex=len(nums)-1
            while lindex<=rindex:
                mid=lindex+(rindex-lindex)//2
                if nums[mid] >= target:
                    rindex=mid-1
                    leftBorder=rindex  # 这里左边界更新
                else:
                    lindex=mid+1  
            return leftBorder            

        leftBorder = getLeftBorder(nums,target)
        rightBorder = getRightBorder(nums,target)
        # 情况一,target不在数组范围内时,以target在数组左侧为例,
        # 二分查找会不断更新rindex的值,那么leftBorder不更新,一直为-2。同理可以推出,target在数组右侧的情况。
        if leftBorder == -2 or rightBorder == -2:
            return [-1,-1]
        # 情况三,因为leftBorder和rightBorder分别位于target的前一个索引位置和后一个索引位置
        # 故 rightBorder-leftBorder必定大于1
        elif rightBorder-leftBorder > 1:
            return [leftBorder+1,rightBorder-1]
        # 情况二
        else:
            return [-1,-1]

参考

代码随想录-34. 在排序数组中查找元素的第一个和最后一个位置

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/599857.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

ASP.NET通用作业批改系统设计

摘  要 该系统采用B/S结构&#xff0c;以浏览器方式登陆系统&#xff0c;用ASP.NET作为开发语言&#xff0c;数据库则使用Microsoft SQL Server 2000实现。《通用作业批改系统》包括了学生子系统、教师子系统、管理员子系统三大模块&#xff0c;该系统主要完成学生&#xff…

LibTorch入坑记--续2

一、安装faiss 我的faiss&#xff0c;用的是曾经安装过的 pip install faiss-gpu1.7 当时搞得环境名称是pni 二、配置环境 三、例子代码 #include <faiss/IndexFlat.h> #include <faiss/Index.h> #include <faiss/VectorTransform.h> #include <faiss/…

Mybatis进阶4-权限管理

权限管理 1.权限 //相当于 职责 2.用户 //相当于 职员&#xff08;职员就职于一个职位&#xff09; 3.角色 //相当于 职位&#xff08;有多个职责&#xff09; 权限管理基础表&#xff1a;权限表&#xff0c;用户表&#xff0c;角色表 问题1&#xff1a;…

SVM直观理解

https://tangshusen.me/2018/10/27/SVM/ https://www.bilibili.com/video/BV16T4y1y7qj/?spm_id_from333.337.search-card.all.click&vd_source8272bd48fee17396a4a1746c256ab0ae SVM是什么? 先来看看维基百科上对SVM的定义: 支持向量机&#xff08;英语&#xff1a;su…

根据最近拒包项目总结,详细讲解Google最新政策(上)

关于占比最多的移动垃圾软件拒审问题 移动垃圾软件(Mobile Unwanted Software)特征表现1> 具有欺骗性,承诺其无法实现的价值主张。2> 诱骗用户进行安装,或搭载在用户安装的其他程序上。3> 不向用户告知其所有主要功能和重要功能。4> 以非预期方式影响用户的系统…

Error Code: 1449. The user specified as a definer (‘admin‘@‘%‘) does not exist

前言 在进行MySQL数据库迁移或存储过程部署时&#xff0c;您可能会遇到错误 [Err] 1449 - The user specified as a definer (admin%) does not exist。这篇文章将为您提供一个详细的解决方案&#xff0c;帮助您顺利解决这一问题。 错误背景 此错误通常发生在尝试执行一个存…

Jenkins集成Kubernetes 部署springboot项目

文章目录 准备部署的yml文件Harbor私服配置测试使用效果Jenkins远程调用参考文章 准备部署的yml文件 apiVersion: apps/v1 kind: Deployment metadata:namespace: testname: pipelinelabels:app: pipeline spec:replicas: 2selector:matchLabels:app: pipelinetemplate:metada…

机器学习算法--朴素贝叶斯(Naive Bayes)

一、实验环境 1. python3.7 2. numpy > 1.16.4 3. sklearn > 0.23.1 二、朴素贝叶斯的介绍 朴素贝叶斯算法&#xff08;Naive Bayes, NB) 是应用最为广泛的分类算法之一。它是基于贝叶斯定义和特征条件独立假设的分类器方法。NB模型所需估计的参数很少&#xff0c;对缺…

【微服务】网关(详细知识以及登录验证)

微服务网关 网关网关路由快速入门路由属性 路由断言网关登录校验自定义过滤器实现登录校验网关传递用户OpenFeign传递用户 网关 网络的关口&#xff0c;负责请求的路由&#xff0c;转发&#xff0c;身份校验 当我们把一个单体项目分成多个微服务并部署在多台服务器中&#xff…

DDR4 新功能介绍

DDR4(第四代双倍数据率同步动态随机存取内存)相较于其前代DDR3,引入了一些新的功能和改进,这些新功能有助于提高内存的性能、降低功耗以及增强系统的可靠性,包括VPP、DBI(Data Bus Inversion,数据总线翻转)和DMI(与LPDDR4相关)。以下是对这些功能的简要说明: 更高的…

java—异常

异常 什么是异常 异常的体系 编译时异常处理方式 1、选择报错的整个代码块&#xff0c;快捷键crtlaltt键&#xff0c;选择try/catch将代码围起来。 2、编译异常处理方式2 在main方法上抛出异常 自定义异常 例子&#xff1a; 自定义运行时异常 自定义编译时异常 异常…

视觉图像信息处理与FPGA实现第九次作业——直方图均衡

RAM的B站视频解析 RAM的文档 一、65536x8位的单端口RAM timescale 1ns / 1ps //SPRF Single Port Read/Write Function //65535 是RAM中总的字数&#xff0c;也就是存储深度&#xff0c;X8表示每个字是8位的 module SPRF65536X8(Q,CLK,CEN,WEN,A,D );//输出寄存器Qoutput [7…

如何在已经安装好的PostgreSQL14中安装uuid 扩展

当前环境 PG14.8 LINUX 8.8 存在问题&#xff1a; 开发人员问&#xff0c;PG中&#xff0c;支持 生成UUID吗&#xff0c;具体是什么&#xff0c;答&#xff0c;类似这个函数 uuid_generate_v4() 看了一下&#xff0c; select uuid_generate_v4();会报错&#xff0…

2024-05-07 商业分析-如何在社会层面做一个更好的工具人-记录

摘要: 2024-05-07 商业分析-如何成为一个靠谱的工具人 如何在社会层面做一个更好的工具人 那么今天讲的这个主题呢&#xff0c;对吧&#xff1f;你们一看啊&#xff0c;就觉得这个就不应该我讲是吧啊&#xff0c;但是呢这个逻辑呢我还得跟你们讲一下啊&#xff0c;就是如何成为…

2009-2022年上市公司华证ESG评级评分数据(含细分项)

2009-2022年上市公司华证ESG评级评分数据&#xff08;含细分项&#xff09; 1、时间&#xff1a;2009-2022年 2、来源&#xff1a;华证ESG 3、指标&#xff1a;证券代码、证券简称、综合评级、年度、综合得分、E评级、E得分、S评级、S得分、G评级、G得分 4、范围&#xff1…

AI伦理和安全风险管理终极指南

人工智能&#xff08;AI&#xff09;正在迅速改变各个领域的软件开发和部署。驱动这一转变的两个关键群体为人工智能开发者和人工智能集成商。开发人员处于创建基础人工智能技术的最前沿&#xff0c;包括生成式人工智能&#xff08;GenAI&#xff09;模型、自然语言处理&#x…

Python读取ASC文件并转换成Excel文件(坐标)

import pandas as pd# 读取asc文件&#xff0c;指定空格为分隔符 df pd.read_csv(out_view2.asc, sep , headerNone)# 去掉空列 df df.dropna(howall, axis1)# 将数据保存到Excel文件 df.to_excel(out_view2.xlsx, indexFalse, headerFalse)效果图

Day1| Java基础 | 1 面向对象特性

Day1 | Java基础 | 1 面向对象特性 基础补充版Java中的开闭原则面向对象继承实现继承this和super关键字修饰符Object类和转型子父类初始化顺序 多态一个简单应用在构造方法中调用多态方法多态与向下转型 问题回答版面向对象面向对象的三大特性是什么&#xff1f;多态特性你是怎…

unity华为sdk接入指路指南

目前比较靠谱的几个方案&#xff1a;试过几个仅供参考 温馨提示&#xff1a;最高目前可支持方案到unity2021版本以下&#xff0c;以上请联系华为官方寻求技术支持 Unity集成华为游戏服务SDK方式&#xff08;一&#xff09;&#xff1a;集成Unity官方游戏SDK&#xff1a; 华为…

代码随想录算法训练营第十八天:二叉树的层序遍历(中间放假)

代码随想录算法训练营第十八天&#xff1a;二叉树的层序遍历&#xff08;中间放假&#xff09; ‍ ​​ 102.二叉树的层序遍历 力扣题目链接(opens new window) 给你一个二叉树&#xff0c;请你返回其按 层序遍历 得到的节点值。 &#xff08;即逐层地&#xff0c;从左到右…