【算法day1】数组:双指针算法

题目引用

这里以
1、LeetCode704.二分查找
2、LeetCode27.移除元素
3、LeetCode977.有序数组的平方
这三道题举例来说明数组中双指针的妙用。

1、二分查找

给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
首先我们来理解一下题意
我们需要在一段连续递增的数组当中找到 ==target 元素,并在函数结尾返回它。
暴力的解法是直接把数组遍历一遍,一一比对,找到后返回。当然时间复杂度会是 O(N) 级别的。
那么有没有更简便的写法呢?
当然有,那就是我们今天要见识到的 双指针算法
首先我们初始化两个指针,一个指向数组的头left,另一个指向数组的尾right。并且维护一个 mid 指针,使其始终处于 [left,right] 范围内,比较数组 mid 位置与target 的数值大小。如果 mid 位置的数值比target大,那么将right移动到mid位置,再次更新mid位置。如果 mid 位置的数值比target小,那么将left移动到mid位置,再次更新mid位置。如此循环直到找到 ==target 值的位置或者 left>right 循环结束。
注意:由于区间的个人喜好不同,一般有左闭右开写法和左闭右闭两种写法。
左闭右开写法:

int search(vector<int>& nums, int target) {int left=0,right=nums.size();while(left<right){int mid=(left+right)>>1;if(target>nums[mid]){left=mid+1;}else if(target<nums[mid]){right=mid;}else{return mid;}}return -1;}

左闭右闭写法:

int search(vector<int>& nums, int target) {int left=0,right=nums.size()-1;while(left<=right){int mid=(left+right)>>1;if(target>nums[mid]){left=mid+1;}else if(target<nums[mid]){right=mid-1;}else{return mid;}}return -1;}

那么这题就被完美地解决了~

2、移除元素

给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k,要通过此题,您需要执行以下操作:

更改 nums 数组,使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
返回 k。

我们来理解一下题意:
给了我们一个存储着随机元素且随机长度的数组,让我们来移除 ==val 的元素,这道题当然可以遍历一遍数组,将数组中 ==val 的元素全部覆盖掉,但是这样是很容易丢失数据位置进而引发结果错误的。那么应该怎么写才能快速而优雅地AC它呢?当然还是双指针。
我们定义两个指针,一个快指针fast,一个慢指针slow。我们让fast指针先走,边走边判断数组中的元素是否 ==val 。如果等于,我们继续往下走(是不是很奇怪?别急,慢慢看),如果 !=val ,我们让fast位置的值和slow位置的值交换,并且 slow++。当fast走到数组末尾的时候,返回slow。
为什么?
为什么slow位置就能代表 !=val 的所有元素的数目呢?
我来画个图给大家看看

初始化
slow++
在这里插入图片描述
交换
在这里插入图片描述
在这里插入图片描述
所以返回slow就会是被移除后的元素数量。
附上代码

int removeElement(vector<int>& nums, int val) {int slow=0;for(int fast=0;fast<nums.size();fast++){if(nums[fast]!=val) nums[slow++]=nums[fast];}return slow;}

这题也就完美的完成啦~

3、有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。

这题我们也分析一下下~
首先用暴力算完再排序也是可以的~但我们是手艺人,不能题题都暴力。
这题也是给我们一个非递减数组,也就是要么增要么等。那么还是使用双指针来解吧。定义一个头指针i,尾指针j,遍历数组,比较 nums[i] , nums[j] 平方后的大小, i 位置的平方比较大就交换,反之则将 平方后的数 放回数组对应位置继续循环。
直接上代码

vector<int> sortedSquares(vector<int>& nums) {int n = nums.size();vector<int> ans(n);int i = 0, j = n - 1;for (int p = n - 1; p >= 0; p--) {int x = nums[i], y = nums[j];if (-x > y) {ans[p] = x * x;i++;} else {ans[p] = y * y;j--;}}return ans;}

总结

双指针算法既简便又能快速解决问题,如果我们遇到数组相关的问题可以积极考虑它。

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

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

相关文章

open-instruct框架使用记录:只使用huggingface数据集的小部分进行训练,如何修改dataset_info.json文件

open-instruct框架 这篇笔记主要记录以下问题&#xff1a;只使用huggingface下载的数据集中的一小部分数据进行数据训练。而且我不想修改open-instruct的加载数据集的代码&#xff0c;以及脚本中的--dataset_mixer_list参数的指定等。下面是我的思路历程。 if args.dataset_na…

Jenkins升级到最新版本后无法启动

1. 场景还原 最近在web界面将jenkins升级到最新版本后&#xff0c;后台无法启动jenkins服务&#xff0c;服务状态如下&#xff1a; 运行jenkins命令提示invalid Java version jenkins --version jenkins: invalid Java version: java version "1.8.0_202" Java(TM)…

DRM(数字权限管理技术)防截屏录屏----ffmpeg安装

提示&#xff1a;ffmpeg安装 文章目录 [TOC](文章目录) 前言一、下载二、配置环境变量三、运行ffmpeg四、文档总结 前言 FFmpeg是一套可以用来记录、转换数字音频、视频&#xff0c;并能将其转化为流的开源计算机程序。采用LGPL或GPL许可证。它提供了录制、转换以及流化音视频的…

Unity版本使用情况统计(更新至2024年11月)

UWA发布&#xff5c;本期UWA发布的内容是第十五期Unity版本使用统计&#xff0c;统计周期为2024年5月至2024年11月&#xff0c;数据来源于UWA网站&#xff08;www.uwa4d.com&#xff09;性能诊断提测的项目。希望给Unity开发者提供相关的行业趋势作为参考。 2024年5月 - 2024年…

Spring Aop 中对JoinPoint的理解

以下是源码中对 JoinPoint 的描述 A runtime joinpoint is an event that occurs on a static joinpoint (i.e. a location in a program). For instance, an invocation is the runtime joinpoint on a method (static joinpoint). The static part of a given joinpoint can…

C中指针在64位操作系统下为什么是4而不是8

好久没写C了&#xff0c;今天用VScode想写个Demo&#xff0c;翻了下指针资料&#xff0c;想打印下指针大小&#xff0c;发现是4&#xff0c;但是理论上64位系统不应该是8么&#xff1f; 结论就是我编的是32位程序&#xff0c;编译器按照32位编译的。 用vscode的C 插件编译运行…

使用 pycharm 新建不使用 python 虚拟环境( venv、conda )的工程

有时候我们发现一个好玩的 demo&#xff0c;想赶快在电脑上 pip install 一下跑起来&#xff0c;发现因为 python 的 venv、conda 环境还挺费劲的&#xff0c;因为随着时间的发展&#xff0c;之前记得很清楚的 venv、conda 的用法&#xff0c;不经常使用&#xff0c;半天跑不起…

鸿蒙主流路由详解

鸿蒙主流路由详解 Navigation Navigation更适合于一次开发,多端部署,也是官方主流推荐的一种路由控制方式,但是,使用起来入侵耦合度高,所以,一般会使用HMRouter,这也是官方主流推荐的路由 Navigation官网地址 个人源码地址 路由跳转 第一步-定义路由栈 Provide(PageInfo) pag…

Flink Sink的使用

经过一系列Transformation转换操作后&#xff0c;最后一定要调用Sink操作&#xff0c;才会形成一个完整的DataFlow拓扑。只有调用了Sink操作&#xff0c;才会产生最终的计算结果&#xff0c;这些数据可以写入到的文件、输出到指定的网络端口、消息中间件、外部的文件系统或者是…

鸿蒙本地模拟器 模拟TCP服务端的过程

鸿蒙模拟器模拟TCP服务端的过程涉及几个关键步骤&#xff0c;主要包括创建TCPSocketServer实例、绑定IP地址和端口、监听连接请求、接收和发送数据以及处理连接事件。以下是详细的模拟过程&#xff1a; **1.创建TCPSocketServer实例&#xff1a;**首先&#xff0c;需要导入鸿蒙…

【VUE3】新版Vue3+ElementPlus全家桶开发视频项目实战

VUE 介绍 Vue (发音为 /vjuː/,类似 view) 是一款用于构建用户界面的 JavaScript 框架。它基于标准 HTML、CSS 和 JavaScript 构建,并提供了一套声明式的、组件化的编程模型,帮助你高效地开发用户界面。 Vue.js是一个MVVM(Model - View - ViewModel)的SPA框架。 Model:数…

Edify 3D: Scalable High-Quality 3D Asset Generation

Deep Imagination Research | NVIDIA 目录 一、Abstract 二、核心内容 1、多视图扩散模型 3、重建模型&#xff1a; 4、数据处理模块&#xff1a; 三、结果 1、文本到 3D 生成结果 2、图像到 3D 生成结果 3、四边形网格拓扑结构 一、Abstract NVIDIA 开发的用于高质量…

Python爬虫能处理动态加载的内容吗?

Python爬虫确实可以处理动态加载的内容。动态加载的内容通常是通过JavaScript在客户端执行&#xff0c;这意味着当网页首次加载时&#xff0c;服务器返回的HTML可能并不包含最终用户看到的内容。相反&#xff0c;JavaScript代码会在页面加载后从服务器请求额外的数据&#xff0…

JavaScript练习2——动态“钟”的绘制

实现效果&#xff1a; 分析需求&#xff1a; 1、需要每隔一定时间间隔执行一次绘图&#xff0c;实现旋转效果 2、需要绘制矩形框、圆形缺口框、文字 3、需要设置style 代码实现&#xff1a; 下面给出关键代码的实现&#xff0c;部分函数在之前的文章已经给出 https://blog.…

Jira使用笔记二 ScriptRunner 验证问题创建角色

背景 最近在对公司Jira工作流改造&#xff0c;收到这么一个要求&#xff1a;某些问题类型只有某些角色可以创建。本来是想通过Jira内建的权限控制来处理的。结果点到权限页面&#xff0c;心都凉透了。 好吧&#xff0c;那只能上脚本了。最终使用ScriptRunner的Simple scripte…

Java中的线程池使用详解

文章目录 Java中的线程池使用详解一、引言二、线程池的创建与使用1、线程池的创建1.1、FixedThreadPool&#xff08;固定大小线程池&#xff09;1.2、CachedThreadPool&#xff08;可缓存线程池&#xff09;1.3、SingleThreadExecutor&#xff08;单线程化线程池&#xff09;1.…

3D扫描对文博行业有哪些影响?

三维扫描技术对文博行业产生了深远的影响&#xff0c;主要体现在以下几个方面&#xff1a; 一、高精度建模与数字化保护 三维扫描技术通过高精度扫描设备&#xff0c;能够捕捉到文物的每一个细节&#xff0c;包括形状、纹理、颜色等&#xff0c;从而生成逼真的3D模型。这些模…

C# 泛型(Generic)

文章目录 前言一、泛型的基本概念与实例展示二、泛型的特性与优势三、泛型方法四、泛型委托 前言 泛型&#xff08;Generic&#xff09;允许将类或方法中编程元素的数据类型规范进行延迟编写&#xff0c;直到在程序实际使用这些类或方法的时候再去确定具体的数据类型。 一、泛…

前端小练习——星辰宇宙(JS没有上限!!!)

前言&#xff1a;在刚开始学习前端的时候&#xff0c;我们会学习到前端三件套中的JavaScript&#xff0c;可能那时候读者没有觉得JavaScript这个语言有多么的牛逼&#xff0c;本篇文章将会使用一个炫酷的案例来刷新你对JavaScript这个语言的认知与理解。 ✨✨✨这里是秋刀鱼不做…

【Python爬虫五十个小案例】爬取豆瓣电影Top250

博客主页&#xff1a;小馒头学python 本文专栏: Python爬虫五十个小案例 专栏简介&#xff1a;分享五十个Python爬虫小案例 &#x1fab2;前言 在这篇博客中&#xff0c;我们将学习如何使用Python爬取豆瓣电影Top250的数据。我们将使用requests库来发送HTTP请求&#xff0c;…