算法之二分查找法和双指针

用二分查找法刷leetcode算法题目的时候,经常遇到视频看着理解很透彻,当上手写时一看就会,一写就废。二分查找法涉及边界条件很多,逻辑很简单,就是写不好。何时写 while(left<right),while(left<=right),还是 right=mid 还是right = mid - 1;等等, 其实我们只要控制区间是左闭右开、还是左闭右闭的条件,定义在区间循环变量不变的原则。
介绍 左闭右开 左闭右闭 这两种写法。
题目:leetcode704
思路:
数组是有序且数据无重复元素,返回下标就唯一,使用二分法的前提条件。若数据中重复元素,返回的下标就不唯一呢。

1、左闭右闭
定义target在左闭右闭区间中**[left, right]中,使用while(left <= right)**的循环条件,即left==right的条件是有意义的![在这里插入图在这里插入图片描述
2、左闭右开

    int left = 0;int  right = numsSize; // 定义target在[left, right) 闭区间中while(left < right) // 当left == right 是无意义的,条件不成立,我们是取不到右边的值,使用 < 号{int mid = left + (right - left) /2; // 防止整数溢出if(nums[mid] == target) { // 找到目标值返回当前下标return mid;} else if(nums[mid] > target) {right = mid; // target在左区间中 在[left, mid)的区间中} else if (nums[mid] < target) {left = mid + 1; // target在右区间中 在[mid+1, right)的区间中}}return -1; // 在当前的区间中没有找到
}

二、双指针
双指针理解: 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
快指针:寻找新数组的元素 ,新数组就是不含有目标元素的数组
慢指针:指向更新 新数组下标的位置
题目 leetcode27
对i--.
对i–,示例2中,对nums[3]覆盖nums[2],导致nums[3]在原数组有下标3变成下标2.但是i向前走了一位,需要保持i原地不动。

在这里插入图片描述
使用双指针:
思路:
1、定义两个指针,用fastIndex遍历与val的值,若存在不相等,用fastIndex对应的下标覆盖val。并移动slowIdex

    int fastIndex = 0;int slowIndex = 0;for(fastIndex; fastIndex < numsSize; fastIndex++){if(nums[fastIndex] != val){nums[slowIndex++] = nums[fastIndex];}}return slowIndex;

leetcode977
思路:
1、定义两个指针,一个指向头,另外一个指向尾。若nums[left] * nums[left] < nums[right] * nums[right], 需要将right–,前移。反之 left++
在这里插入图片描述

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

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

相关文章

通过写文件方式写入 Hive 数据

通过写文件方式写入 Hive 数据 Hive最简单的写入数据方式就是通过Hive Jdbc写入Hive数据&#xff0c;但这并不是写入Hive最高效的方法。 Hive通过读取相关Hdfs的文件来获取数据信息&#xff0c;而通过直接写入Hdfs文件数据达到写入Hive数据的效果&#xff0c;这是目前最高效的…

nerfstudio半离线配置踩坑记录

安装torch2.1.2 with cuda11.8 由于清华镜像源&#xff08;包括阿里源和豆瓣源&#xff09;都没有torch2.1.2cu118的包&#xff0c;因此只能从pytorch官网下载。 服务器上直接通过下面pip的方式安装会由于网络原因中断&#xff0c;无奈只能在本地先把torch的包下载下来再上传到…

SAP与生产制造MPM系统集成案例

一、需求介绍 某公司为保证企业内部生产管理系统的多项基础数据的同步更新&#xff0c;确保各模块间信息的一致性和准确性&#xff0c;对后续的生产计划和物料管理打下基础&#xff0c;该公司将MPM系统和SAP系统经过SAP PO中间件集成平台进行了集成。MPM全称为Manufacturing…

blender--二维平面图标变为三维网格

有时候我们希望把一些二维图片能变成三维网格&#xff0c;本案例我们就针对这一场景进行实现。 首先我们可以先去找一张需要的图片(注意&#xff0c;本例需要图片是svg格式)&#xff0c;我们可以在阿里巴巴矢量图标库等平台进行搜索&#xff0c;如图所示&#xff0c;找到需要的…

diffusion model(扩散模型)DDPM解析

DDPM 前向阶段 重复 2-5 步骤 x 0 ∼ q ( x 0 ) \mathbf{x}_0\sim q(\mathbf{x}_0) x0​∼q(x0​)从数据集中采样一张图片 t ∼ U n i f o r m ( { 1 , … , T } ) t\sim\mathrm{Uniform}(\{1,\ldots,T\}) t∼Uniform({1,…,T})&#xff0c;从 1~T 中随机挑选一个时间步 t ϵ …

三种tcp并发服务器实现程序

都需先进行tcp连接 1、多进程并发 2、多线程并发 3、IO多路复用并发 &#xff08;1&#xff09;select &#xff08;2&#xff09;epoll

SAP ERP与长城汽车EDI业务集成案例(SAP CPI平台)

一、项目背景 某智能座舱公司是国内领先的智能座舱领域科技公司&#xff0c;致力于成为智能网联行业变革的领导者和推动者&#xff0c;聚焦整车域控制器产品、智能网联软件产品和运营服务产品&#xff1b; 已建成首条先进的数智化域控制器生产线&#xff0c;为客户提供最优…

大刀阔斧改革之后,阅文距离“东方迪士尼”更近了吗?

当前&#xff0c;网文IP的确是“富矿”。中国社会科学院文学研究所发布的《2023中国网络文学发展研究报告》显示&#xff0c;截至2023年底&#xff0c;网络文学IP市场规模2605亿元&#xff0c;同比增长近百亿元。 近日&#xff0c;网文产业中的头部企业阅文集团也披露数据称&a…

Android U WMShell动画调用堆栈

本文主要简单介绍WMShell动画调用堆栈 代码环境&#xff1a;repo init -u https://mirrors.tuna.tsinghua.edu.cn/git/AOSP/platform/manifest -b android-14.0.0_r7 Systemserver侧 TAG: at com.android.server.wm.Transition.onTransactionReady(Transition.java:1575) TA…

爆改YOLOv8|利用分层特征融合策略MSBlock改进yolov8,暴力涨点

1&#xff0c;本文介绍 MSBlock 是一种分层特征融合策略&#xff0c;用于改进卷积神经网络中的特征融合效果。它通过分层次地融合不同尺度的特征图来提高网络的表达能力和性能。MSBlock 采用多尺度特征融合的方法&#xff0c;确保网络能够有效地捕捉不同层次和尺度的信息&…

Neo4j导入csv数据,并创建节点

Neo4j 是一种图数据库&#xff0c;特别适合管理和分析复杂的关系数据。 数据来源&#xff1a;http://openkg.cn/ 导入到 Neo4j 的合适场景&#xff1a; 需要在物种分类中查找层级关系&#xff08;如物种的科、属等&#xff09;。 需要进行关系查询和图结构的分析。 想在分类树…

【Axure高保真原型】输入框控制多选下拉列表选项

今天和大家分享输入框控制多选下拉列表选项选项的原型模板&#xff0c;效果包括&#xff1a; 点击下拉框可以弹出选项列表&#xff0c;点击可以切换选中或取消选中 根据选中项在外框出自动生成标签&#xff0c;可以自适应调整高度 下拉列表的选项由左侧多行输入框里的内容控制…

数据结构—— 再探二叉树

1. TOP-K问题 TOP-K问题&#xff1a;求数据结合中前K个最大或者最小的数据 比如&#xff1a;专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等 思路&#xff1a; 1. 用数据集合中前K个数据来建堆&#xff1a; …

WEB服务器-Nginx源码安装及相关配置

一、web服务的常用种类 Apache HTTP Server 简介&#xff1a;Apache是一款广泛使用的Web服务器软件&#xff0c;支持多种操作系统&#xff0c;包括Linux。​​​​​​​特点&#xff1a; 支持多个虚拟主机。 模块化架构&#xff0c;可以根据需要加载不同的模块。 强大的安全…

多态(虚构的整体,具体的个体)(多态的基本概念/多态的原理剖析/纯虚函数和抽象类/虚析构和纯虚析构)

多态的基本概念 #define _CRT_SECURE_NO_WARNINGS #include<iostream> using namespace std; // 多态的基本概念 // 多态分为静态多态和动态多态 // 静态多态&#xff1a; 函数重载还运算符重载属于静态多态&#xff0c;服用函数名 // 动态多态&#xff1a; 派生派和虚函…

VUE使用websocket

在之前搭建好的项目的基础上新版security demo&#xff08;二&#xff09;前端-CSDN博客 目录 一、代码改造 1、后端改造 2、VUE使用websocket 3、测试 二、按用户推送 1、完整代码如下 1.1、前端 1.2、后端&#xff1a; 2、测试 一、代码改造 1、后端改造 &#x…

逆波兰表达式

简介 介绍逆波兰表达式之前&#xff0c;先介绍一下运算种类。 中缀运算与后缀运算 中缀运算是一种常用的算术和逻辑公式表示方法&#xff0c;其中操作符位于两个运算数之间。例如&#xff0c;在表达式 “3 2” 中&#xff0c;加号&#xff08;&#xff09;是操作符&#xf…

算法设计:实验一分治与递归

【实验目的】 深入理解分治法的算法思想&#xff0c;应用分治法解决实际的算法问题。 【实验内容与要求】 设有n2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表&#xff1a; 1.每个选手必须与其他n-1个选手各赛一次&#xff1b;2.每个选手一天只能赛一…

Mysql 集群技术

目录 一 Mysql 在服务器中的部署方法 1.1 在Linux下部署mysql 1.1.1 安装依赖性并解压源码包&#xff0c;源码编译安装mysql&#xff1a; 1.1.2 部署mysql 二 mysql的组从复制 2.1 配置mastesr和salve 测试结果 2.2 当有数据时添加slave2 2.3 延迟复制 2.4 慢查询日志…

【C++ | 设计模式】简单工厂模式的详解与实现

1.简单工厂模式概述 简单工厂模式&#xff08;Simple Factory Pattern&#xff09;是一种创建型设计模式&#xff0c;它定义了一个工厂类&#xff0c;由这个类根据提供的参数决定创建哪种具体的产品对象。简单工厂模式将对象的创建逻辑集中到一个工厂类中&#xff0c;从而将对…