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

一、数组

数组特点:

  • 连续内存空间
  • 存储得数据元素类型一致
  • 数组可以通过下标索引查找数据元素,可以删除、替换、添加元素等

1.1 二分查找

使用二分查找需满足得条件:

  • 数组是有序的;
  • 数组中没有重复元素;
  • 查找的target是唯一的。
  • 注意写代码时数组左右区间。
  1. 题目链接
      给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
    python:
# [left,right]查找区间是左闭右闭
class Solution:def search(self, nums: List[int], target: int) -> int:def run(lindex,rindex):if lindex > rindex:return -1mid=lindex+(rindex-lindex)//2if nums[mid] == target:return midelif nums[mid] > target:rindex=mid-1else:lindex=mid+1return run(lindex,rindex)return run(0,len(nums)-1)

c++版代码:

class Solution {
public:int search(vector<int>& nums, int target) {int lindex=0;int rindex=nums.size()-1;while(lindex <= rindex){int mid=lindex+(rindex-lindex)/2;if(nums[mid] > target)rindex=mid-1;else if(nums[mid] < target)lindex=mid+1;elsereturn mid;}return -1;}
};
  1. 题目链接
      给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
    请必须使用时间复杂度为 O(log n) 的算法
    暴力解法
class Solution:def searchInsert(self, nums: List[int], target: int) -> int:for i in range(len(nums)):# 因为nums是升序数组,故出现的第一个大于或等于target的索引满足条件if nums[i]>=target:return i# 若上述均不满足,说明target大于nums数组全部元素# 故将target插到数组尾部return len(nums) 

二分查找
  首先下述讨论均以左闭右闭区间为例。设定lindex、rindex、mid分别为左边索引、右边索引、中间索引,根据二分查找规则,若数组中没有target,则有lindex>rindex,且lindex=rindex+1。
  根据题意,可分为四种情况:
  (1) 若target小于数组全部元素,故lindex不更新,lindex=0,rindex最终为-1,target插入的索引为0;
  (2) 若target大于数组全部元素,则rindex不更新,rindex=n-1,lindex最终更新的n,target插入的索引为n;
  (3) 若target等于数组中某个元素,则根据二分查找规则,直接返回mid索引即可;
  (4) 若target需插入数组中某个位置,根据上述暴力求解法可以看出,target肯定会插在第一个大于target的索引位置上。根据左闭右闭区间规则,最终target因为不在数组中,则有lindex>rindex跳出循环,此时看下图可知,lidnex左侧的元素必定小于target,则lindex是第一个大于target的索引;从rindex角度来看,rindex右侧的元素必定大于target,故lindex是第一个大于target的索引。故target插入的索引为lindex或者是rindex+1;
在这里插入图片描述

图像参考自https://leetcode.cn/circle/discuss/ooxfo8/

代码:

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

总结

  1. 目前只关注二分查找左闭右闭区间情况,怕与其他情况弄混。之后熟悉了可以再看其他解法;
  2. 第2题对于最终返回的是lindex或者rindex+1,我困惑许久,不太懂为何会是这样的结果。究其根本还是对二分查找算法不够理解,经过多方查找资料才对上述结果有了一定的理解。
    在这里插入图片描述
图像参考自https://leetcode.cn/circle/discuss/ooxfo8/

有如下结论:对于左闭右闭区间情况,

  • 初始状态:lindex=0,rindex=n-1;
  • 循环条件:lindex<=rindex;
  • 中间值索引:mid=lindex+(rindex-lindex)//2;
  • nums[mid] > target, update>> rindex=mid-1;
  • nums[mid] < target, update>> lindex=mid+1;
  • 满足条件:return mid;
  • 跳出循环:lindex>rindex 且 lindex=rindex+1;

参考:

  1. https://www.programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html#%E6%80%9D%E8%B7%AF
  2. https://programmercarl.com/0035.%E6%90%9C%E7%B4%A2%E6%8F%92%E5%85%A5%E4%BD%8D%E7%BD%AE.html#%E6%80%9D%E8%B7%AF
  3. https://leetcode.cn/circle/discuss/ooxfo8/

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

[Docker]容器的网络类型以及云计算

目录 知识梗概 1、常用命令2 2、容器的网络类型 3、云计算 4、云计算服务的几种主要模式 知识梗概 1、常用命令2 上一篇已经学了一些常用的命令&#xff0c;这里补充两个&#xff1a; 导出镜像文件&#xff1a;[rootdocker ~]# docker save -o nginx.tar nginx:laster 导…

关于Oracle 23ai 你要知道的几件事情

1.版本生命周期 23ai发布后的Oracle版本生命周期图&#xff0c;可以看到23ai是长期支持版本可以到2032年。 引申 Oracle版本分为两类 Innovation Release--创新版本&#xff0c;一般提供至少两年技术支持 Long Term Release --长期支持版本&#xff0c;一般提供5年premier和…

护眼灯排名前十的品牌有哪些?护眼灯品牌排行前十名推荐

近视在儿童中愈发普遍&#xff0c;许多家长开始认识到&#xff0c;除了学业成绩之外&#xff0c;孩子的视力健康同样重要。毕竟&#xff0c;学业的落后可以逐渐弥补&#xff0c;而一旦孩子近视&#xff0c;眼镜便可能成为长期伴随。因此&#xff0c;专业的护眼台灯对于每个家庭…

MySQL 中的HASH详解

MySQL中的哈希索引&#xff08;Hash Index&#xff09;是一种特殊的数据库索引类型&#xff0c;它利用哈希表&#xff08;Hash Table&#xff09;的数据结构来存储索引项。哈希表通过哈希函数&#xff08;Hash Function&#xff09;将索引列的值转化为一个固定长度的哈希码&…

腾锐D2000-8 MXM VPX,全国产,可广泛应用于边缘计算网关、入侵检测、VPN、网络监控等等应用领域

腾锐D2000-8 MXM VPX 1. 概述 XMVPX-108 是一款基于飞腾 D2000/8 处理器的低功耗逻辑运算和图形处理 VPX 刀片&#xff0c; 板贴 32GB DDR4 内存&#xff0c;搭载飞腾 X100 套片&#xff0c;满足通用 IO 接口功能。GPU 采用 MXM 小型插卡形式&#xff0c; 搭配 8GB 显卡。提供…

SAP 定义冻结库存不参与MRP运算简介

在MRP中,有着各种类型的特殊库存,在运行MRP时,某些特殊库存将被考虑,某些特殊库存又不被考虑,在实际过程中某个物料的库存,存在冻结库存,质检库存,调拨的在途库存,业务部门并不希望一味的将库存地点排除到MRP计算之外。希望在跑MRP的时候只考虑非限制库存。 针对以上…

使用STM32的FLASH保存数据

使用STM32的FLASH保存数据 为了防止“掉电丢失数据”&#xff0c;我们最先想到的是EEPROM&#xff0c;但是若考虑到降低成本和PCB布线的空间&#xff0c;使用CPU内部的FLASH空间来保存数据&#xff0c;是最好的选择。尤其是在STM32芯片上&#xff0c;应用案例还是比较多的。 …

使用Beego创建API项目并自动化文档

最近需要使用Go写一个Web API项目&#xff0c;可以使用Beego与Gin来写此类项目&#xff0c;还是非常方便的&#xff0c;这里就介绍一下使用Beego来创建的Web API项目并自动化文档的方法。 使用Gin创建API项目并自动化文档参见&#xff1a;使用Gin编写Web API项目并自动化文档 …

软件FMEA的时机:架构设计、详设阶段——FMEA软件

免费试用FMEA软件-免费版-SunFMEA 软件FMEA&#xff08;故障模式与影响分析&#xff09;是一种预防性的质量工具&#xff0c;旨在识别软件中可能存在的故障模式&#xff0c;并分析其对系统性能、安全性和可靠性的影响。在软件开发生命周期中&#xff0c;选择适当的时机进行FME…

十七岁少女夸小沈阳:我瞅你长得有一种大海的感觉呢!

十七岁少女夸小沈阳&#xff1a;我瞅你长得有一种大海的感觉呢&#xff01; ——小品《超级大明星》&#xff08;上&#xff09;的台词 小沈阳&#xff1a;THANK YOU 哦了 不用拍 感谢大家 非常的感谢所有的好朋友们 把你们热情而洋溢的掌声呢 送给我们所有的演员 这…

[VulnHub靶机渗透] Hackademic: RTB1

&#x1f36c; 博主介绍&#x1f468;‍&#x1f393; 博主介绍&#xff1a;大家好&#xff0c;我是 hacker-routing &#xff0c;很高兴认识大家~ ✨主攻领域&#xff1a;【渗透领域】【应急响应】 【Java、PHP】 【VulnHub靶场复现】【面试分析】 &#x1f389;点赞➕评论➕收…

linux内核网络源码--通知链

内核的很多子系统之间有很强的依赖性&#xff0c;其中一个子系统侦测到或者产生的事件&#xff0c;其他子系统可能都有兴趣&#xff0c;为了实现这种交互需求&#xff0c;linux使用了所谓的通知链。 本章我们将看到 通知链如何声明以及网络代码定义了哪些链 内核子系统如何向通…

【yolov8】yolov8剪枝训练流程

yolov8剪枝训练流程 流程&#xff1a; 约束剪枝微调 一、正常训练 yolo train model./weights/yolov8s.pt datayolo_bvn.yaml epochs100 ampFalse projectprun nametrain二、约束训练 2.1 修改YOLOv8代码&#xff1a; ultralytics/yolo/engine/trainer.py 添加内容&#…

深度学习之基于Vgg19预训练卷积神经网络图像风格迁移系统

欢迎大家点赞、收藏、关注、评论啦 &#xff0c;由于篇幅有限&#xff0c;只展示了部分核心代码。 文章目录 一项目简介 二、功能三、系统四. 总结 一项目简介 一、项目背景 在数字艺术和图像处理领域&#xff0c;图像风格迁移技术一直备受关注。该技术可以将一幅图像的内容和…

MATLAB实现杜拉德公式和凯夫公式的计算固液混合料浆临界流速

MATLAB实现杜拉德公式和凯夫公式的计算固液混合料浆临界流速: 杜拉德公式是用来计算非均质固液混合料浆在输送管中的临界速度的公式&#xff0c;具体形式为&#xff1a; uL FL (2gD / (ρ0 - ρ1))^(1/2) 其中&#xff1a; uL&#xff1a;表示料浆的临界速度&#xff0c;…

什么是泛域名证书?与普通SSL证书有什么区别

随着互联网的发展&#xff0c;越来越多的网站开始使用SSL证书来保护用户的隐私和安全。在SSL证书中&#xff0c;泛域名SSL证书和普通域名证书是两种常见的类型。那么&#xff0c;什么是泛域名SSL证书&#xff0c;与普通域名证书有什么区别呢&#xff1f; 首先&#xff0c;我们来…

投资者悄然收购二手楼梯楼,在杭州豪掷巨资购买12套!

独家首发 -------------- 日前杭州中介流传&#xff0c;一名投资客大举收购二手楼梯楼&#xff0c;下手就是12套&#xff0c;显示出一些具有前瞻性眼光的投资者悄悄放弃电梯楼&#xff0c;选择了处于价格洼地的楼梯楼。 二手楼梯楼当下被严重低估&#xff0c;在一线城市的二手楼…

【文献阅读】 The ITS Irregular Terrain Model(Longely-Rice模型)海上电波传播模型

前言 因为最近在做海上通信的一个项目&#xff0c;所以需要对海上的信道进行建模&#xff0c;所以才阅读到了这一篇文献&#xff0c;下面的内容大部分是我的个人理解&#xff0c;如有错误&#xff0c;请见谅。欢迎在评论区和我一起讨论。 Longely-Rice模型介绍 频率介于 20 …

AI摄影教程,让你实现写真自由!

AI摄影&#xff0c;就是用AI生成写真照片 和传统摄影不同的是&#xff0c;传统的摄影需要先妆造、布景&#xff0c;然后再进行拍摄&#xff0c;前后需要耗费的时间精力非常多 而AI摄影只需要在电脑上上传十几张自己的日常照片&#xff0c;就能根据自己的喜好去生成各种梦幻、甚…

软件测试经理工作日常随记【2】-接口自动化

软件测试主管工作日常随记【2】-接口自动化 1.接口自动化 jmeter-反电诈项目 这个我做过的一个非常有意义的项目&#xff0c;和腾讯合作的&#xff0c;主要为用户拦截并提示所有可能涉及到的诈骗类型&#xff0c;并以裂变的形式扩展用户&#xff0c;这个项目前期后端先完成&…