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

server/2024/11/28 9:04:14/

题目引用

这里以
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.ppmy.cn/server/145581.html

相关文章

创建可重用React组件的实用指南

尽管React是全球最受欢迎和使用最广泛的前端框架之一&#xff0c;但许多开发者在重构代码以提高可复用性时仍然感到困难。如果你发现自己在React应用中不断重复相同的代码片段&#xff0c;那你来对地方了。 在本教程中&#xff0c;将向你介绍三个最常见的特征&#xff0c;表明是…

路由策略与路由控制实验

AR1、AR2、AR3在互联接口、Loopback0接口上激活OSPF。AR3、AR4属于IS-IS Area 49.0001&#xff0c;这两者都是Level-1路由器&#xff0c;AR3、AR4的系统ID采用0000.0000.000x格式&#xff0c;其中x为设备编号 AR1上存在三个业务网段A、B、C&#xff08;分别用Loopback1、2、3接…

Z2400024基于Java+SSM+mysql+maven开发的社区论坛系统的设计与实现(附源码 配置 文档)

基于SSM开发的社区论坛系统 1.摘要2.主要功能3.系统运行环境4.项目技术5.系统界面截图6.源码获取 1.摘要 本文介绍了一个基于SSM&#xff08;Spring、Spring MVC、MyBatis&#xff09;框架开发的社区论坛系统。该系统旨在打造一个高品质的开发者社区&#xff0c;为开发者提供一…

详解 PyTorch 中的 DataLoader:功能、实现及应用示例

详解 PyTorch 中的 DataLoader&#xff1a;功能、实现及应用示例 在 PyTorch 框架中&#xff0c;Dataloader 是一个非常重要的类&#xff0c;用于高效地加载和处理来自 Dataset 的数据。Dataloader 允许批量加载数据&#xff0c;支持多线程/多进程加载&#xff0c;并可进行数据…

从web前端角度浅析网络安全

摘 要 当前网络与信息技术已经有了非常大的进步﹐Web前端技术的使用、和其安全问题也越来越受到我们的重视。 Web前端技术毫无疑问是网络技术的入口&#xff0c;是我们互联网的门户&#xff0c;也是网络安全中最容易被攻击的环节&#xff0c;经常受到黑客的青睐。因此&…

DeepSpeed 配置文件(DeepSpeed Configuration Files)详解:中英文解释

中文版 本文详细介绍 DeepSpeed 配置文件&#xff0c;结合 4 卡 3090 的实际使用场景&#xff0c;重点解释各个参数的含义&#xff0c;并提供应对爆显存的方案。 DeepSpeed 配置文件详解&#xff1a;从基础到实战 DeepSpeed 是用于加速大规模分布式训练的重要工具&#xff0c…

identify的环境设置以及报错解决方法(二)

4.error当点run的时候,出现error Project is not distributed 工程不是分布式的,这一般有2个原因 第一个原因是下载的Bit和加载的idenify文件不匹配,核对你下载的Bit文件和你加载的synaplify.prj是否是一个工程,如果是,那可能是第二种情况 第二个原因就是identify…

【VUE】el-table表格内输入框或者其他控件规则校验实现

1、封装组件 1、规则校验一般基于form表单实现&#xff0c;因此需要给具体控件套一层form表单 新建组件input-required.vue&#xff0c;内容如下 <template><div><el-form ref"formRef" :model"form" :rules"formRules" label-…