【面试经典150题】删除有序数组中的重复项||

在这里插入图片描述

目录

  • 一.题目解析
    • 二.解法一
      • 三.解法二

一.题目解析

首先我们先看一下题目描述:
在这里插入图片描述
删除数组中的重复项的升级版要求,一个升序数组序列中,相同的元素最多出现两次。

二.解法一

首项我们先来看一种比较繁琐坑比较多的解法:

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() < 3) {
            return nums.size();
        }
        auto a1 = nums.begin();
        auto a2 = nums.begin() + 1;
        auto a3 = nums.begin() + 2;

        while (a3 != nums.end()) {
            while ((a2 + 1) != nums.end() && *a1 == *a2 && *a2 == *a3) {
                if (a3 == nums.end()) {
                    break;
                }
                nums.erase(a3);
            }
            if ((a2 + 1) == nums.end())
                break;
            a1++;
            a2++;
            a3++;
        }
        return nums.size();
    }
};

首先当数组大小小于3时,这时的数组数据无论是什么都会满足题目的要求,所以直接返回即可。接下来在while的处理中如果a1等于了a3的数据我们则删除a3,其中涉及指针的越界访问会比较麻烦。这个解法简单了解下即可。

三.解法二

解法二我们运用到了双指针的知识:


class Solution {
    public: int removeDuplicates(vector<int>& nums) {
        if(nums.size()<3)
        {
            return nums.size();
        }
        int f = 0;
        for (int b = f + 2; b < nums.size(); b++) {
            if (nums[f] != nums[b]) {
                nums[f + 2] = nums[b];
                f++;
            }
        }
        return f + 2;
    }
};


首先同样数组大小小于3时直接返回即可,我们用f来表示已经处理好了数组长度,b用来表示遍历的进度。-2则代表了题目要求的最多连续两个相同元素。大家可以调试体会一下,一般这题即是想到双指针也会使用计数的方法,上面的解法还是很巧妙的。

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

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

相关文章

JCR一区级 | Matlab实现TCN-BiLSTM-MATT时间卷积双向长短期记忆神经网络多特征分类预测

JCR一区级 | Matlab实现TCN-BiLSTM-MATT时间卷积双向长短期记忆神经网络多特征分类预测 目录 JCR一区级 | Matlab实现TCN-BiLSTM-MATT时间卷积双向长短期记忆神经网络多特征分类预测分类效果基本介绍程序设计参考资料 分类效果 基本介绍 1.JMatlab实现TCN-BiLSTM-MATT时间卷积双…

Spring Boot 整合开源 Tess4J库 实现OCR图片文字识别

&#x1f604; 19年之后由于某些原因断更了三年&#xff0c;23年重新扬帆起航&#xff0c;推出更多优质博文&#xff0c;希望大家多多支持&#xff5e; &#x1f337; 古之立大事者&#xff0c;不惟有超世之才&#xff0c;亦必有坚忍不拔之志 &#x1f390; 个人CSND主页——Mi…

Python | 试卷刷题and基础笔记

1.下列转义字符中&#xff0c; 属于“回车”含义的是 \n 换行 \r 回车 2.for循环遍历字典 在Python中&#xff0c;你可以使用for循环来遍历字典的键&#xff08;keys&#xff09;、值&#xff08;values&#xff09;或者键-值对&#xff08;items&#xff09;。下面是三种遍历…

RPA机器人未来的发展方向和趋势

在数字经济的大背景下&#xff0c;众多企业重新寻找自身的创新驱动力&#xff0c;数字化转型需求迎来爆发式增长。在强劲的数字化转型需求以及国家政策的推动下&#xff0c;RPA行业即将迎来更为有利的发展局面。Gartner预测&#xff0c;到2025年&#xff0c;超级自动化市场规模…

【JavaScript】---DOM操作1:获取元素

【JavaScript】—DOM操作1&#xff1a;获取元素 文章目录 【JavaScript】---DOM操作1&#xff1a;获取元素一、什么是DOM&#xff1f;1.1 概念1.2 图例演示 二、查找HTML元素2.1 getElementById()2.2 getElementsByTagName()2.3 getElementsByClassName()2.4 querySelector()2.…

成人本科毕业论文怎么写?分享自己的经验

撰写成人本科毕业论文是一个系统而深入的过程&#xff0c;以下是我个人的经验分享&#xff0c;希望能帮助你更好地完成这一任务&#xff1a; 1. 明确论文选题 兴趣与专长&#xff1a;选择自己感兴趣且有一定专长的领域&#xff0c;这样更容易深入研究。可行性&#xff1a;确保…

NocoDB开源的智能表格详解-腾讯文档本地替代品

文章目录 一、介绍二、docker-compose部署三、登录NocoDB四、NocoDB手册1. 创建项目2. 收集统计表2.1 添加字段2.2 编辑字段2.3 字段类型2.4 发布表格 3.创建表单3.1 创建表单3.2 分享表单3.3 填写检测单 4.创建看板5.创建画廊 一、介绍 可作为腾讯文档的本地电子表格替代品&a…

Springboot作业管理系统的设计与实现-计算机毕业设计源码98119

目 录 摘要 1 绪论 1.1研究背景 1.2研究现状 1.3springboot框架介绍 1.4论文结构与章节安排 2 作业管理系统系统分析 2.1 可行性分析 2.1.1 技术可行性分析 2.1.2 经济可行性分析 2.1.3 法律可行性分析 2.2 系统功能分析 2.2.1 功能性分析 2.2.2 非功能性分析 2…

论文摘要一般要写些什么内容?

论文摘要通常需要包含以下几个关键内容&#xff1a; 研究背景与目的&#xff1a;简要介绍研究的背景信息&#xff0c;包括研究领域的重要性、当前的研究现状以及存在的问题。然后&#xff0c;清晰地阐述研究的目的、研究问题或研究假设&#xff0c;让读者明白研究的出发点和意图…

python 各种画图(2D 3D)-1 _matplotlib 官方网站笔记

背景 需利用python进行3D可视化处理&#xff0c;用于分析python得到的数据的正确性。 知识学习 python高阶3D绘图---pyvista模块&#xff0c;mayavi模块&#xff0c;pyopengl模块&#xff0c;MoviePy模块基础使用-CSDN博客 python用于3D绘图的模块比较多&#xff0c;pyvist…

Apache Doris 基础 -- 数据表设计(表索引)

1、索引概述 索引用于帮助快速过滤或搜索数据。目前&#xff0c;Doris支持两种类型的索引:内置智能索引和用户创建的二级索引。 内置智能索引 排序键和前缀索引:Apache Doris基于排序键以有序的方式存储数据。它为每1024行数据创建一个前缀索引。索引中的键是当前1024行组的…

2024码蹄杯初赛 拔河(非二分解法)

AK选手前来补充一发邪典&#xff08;水数据&#xff09;写法 题面&#xff1a; 简单来说就是给你一个序列&#xff0c;让你选择一段连续区间&#xff0c;使得这个区间平均值最大&#xff0c;同时区间长度大于等于F。 很显然对于区间求和直接用前缀和优化到O(1)&#xff0c;但是…

代码随想录 day 26

回溯 组合总和 题意&#xff1a;一个无重复元素的整数数组&#xff1b;一个目标整数target&#xff1b; 找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 &#xff1b;并以列表形式返回。candidates 的同一个数字可以无限制重复被选取。 思路&#xff1a;因为…

半导体光子电学期末笔记2: 光子晶体 Photonic crystals

光子晶体概述 光子晶体定义和分类 [P4-5] 光子晶体是一种在一维、二维或三维空间内周期性排列的多层介质。这些结构通过在光子尺度上排列的重复单元&#xff0c;可以对光进行调控和控制。具体来说&#xff0c;光子晶体是指那些在空间上具有周期性排列的介质结构&#xff0c;它…

文心一言 VS 讯飞星火 VS chatgpt (273)-- 算法导论20.2 8题

八、假设设计了这样一个 proto-vEB 结构&#xff0c;其中每个簇数组仅有 u 1 4 u^\frac{1}{4} u41​ 个元素。那么每个操作的运行时间是多少&#xff1f;如果要写代码&#xff0c;请用go语言。 文心一言&#xff1a; 如果你修改了 van Emde Boas (vEB) 树中的簇大小&#xf…

贪心算法题实战详解

文章目录 例题1&#xff1a;活动安排问题例题2&#xff1a;货币找零问题例题3&#xff1a;分数背包问题&#xff08;部分背包问题&#xff09;例题4&#xff1a;最小生成树问题&#xff08;Prim算法&#xff09;例题5&#xff1a;哈夫曼编码例题6&#xff1a;活动选择问题例题7…

KAN(Kolmogorov-Arnold Network)的理解 3

系列文章目录 第一部分 KAN的理解——数学背景 第二部分 KAN的理解——网络结构 第三部分 KAN的实践——第一个例程 文章目录 系列文章目录前言KAN 的第一个例程 get started 前言 这里记录我对于KAN的探索过程&#xff0c;每次会尝试理解解释一部分问题。欢迎大家和我一起讨…

Spring 之 Lifecycle 及 SmartLifecycle

最近在看Eureka源码&#xff0c;本想快速解决这场没有硝烟的战役&#xff0c;不曾想阻塞性问题一个接一个。为正确理解这个框架&#xff0c;我不得不耐着性子&#xff0c;慢慢梳理这些让人困惑的点。譬如本章要梳理的Lifecycle和SmartLifecycle。它们均为接口&#xff0c;其中后…

【TB作品】MSP430F149单片机,广告牌,滚动显示

LCD1602滚动显示切换播放暂停字符串 显示Public Places 显示No Smoking 播放 暂停 部分代码 char zifu1[] "Public Places "; char zifu2[] "Class Now "; char zifu3[] "No admittance "; char *zifu[] { zifu1, zifu2, zifu3 }…

【kafka】关于Kafka的入门介绍

为什么要使用kafka&#xff1f;kafka是什么东西&#xff1f; 案例场景 A服务向B服务发送消息&#xff0c;A服务传输数据很快&#xff0c;B服务处理数据很慢&#xff0c;这样B服务就会承受不住&#xff0c;怎么办&#xff1f;通过添加消息队列作为缓冲。kafka就是消息队列中的…