首页 > 其他分享 >【practise】删除有序数组中的重复项

【practise】删除有序数组中的重复项

时间:2024-08-06 21:25:20浏览次数:13  
标签:slow 删除 nums 元素 fast 数组 practise 指针

关于博主:

在这里插入图片描述

今天分享一道简单的关于“双指针”算法的题目。算是双指针中非常基础的题目,有兴趣可以借鉴一波~

目录

1.题目介绍

题目链接:LINK
在这里插入图片描述

本题要求是:对给定的有序数组nums删除重复元素,使得每种元素仅在该数组中出现一次,并返回新的数组长度。请注意,上述操作必须在原数组中进行(即使用O(1)空间复杂度去解决此问题)。

2.题解思路:双指针法

给定数组是有序的,任何相同的元素均相邻。 题目中介绍,这是一个非严格递增的数组,变相告诉我们该数组是有序的,因此我们可以推的该数组中所有重复元素按均相邻。
在这里插入图片描述

特殊情况,数组元素个数为0时返回0。 nums为0,则证明没有任何元素,可以直接返回0(这点题目中没有明确说明)。

一般情况,数组元素个数大于0。 一般情况下,数组中至少有一个元素,因此在删除重复元素之后也会至少剩下一个元素,因此我们可知nums[0]保持原样即可,不必修改,因为nums[0]是删除后一定存在的。因此我们从下标1处开始检查并删除元素。
在这里插入图片描述

快慢指针法:指定两个指针,一个fast指针(快指针)用于在数组前面遍历检查,另一个slow指针(满指针)用于把表示下一个不同元素填入指定下标位置。初始情况下,fast指向1(0处不用进行检查,因为必定不会被删除),slow指向0。
假设数组的总长度为n,按照快慢指针法快指针将依次遍历下标1-n-1处的数字,当检查到与slow位置的值不相同时,则++slow,把该不同的数据填入到slow位置下;如果fast指针遍历到的数字与slow相同,那么我们继续fast++;
在这里插入图片描述

返回值:遍历结束后,我们slow指向的位置及前面所有位置均是有效数字,我们返回slow + 1即可。
在这里插入图片描述

3.代码示例

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        // 双指针法解答
        int slow = 0, fast = 1;//快慢指针

        while(fast < nums.size())
        {
            if(nums[fast] != nums[slow])//如果快指针对应的值不等于慢指针
            {
                nums[++slow] = nums[fast];//满指针先++,再把不同的值拷贝给nums[slow]
            }
           
           fast++;//继续遍历下一个
        }

        return slow + 1;//返回慢指针+1
    }
};

不知你是否还有更好的思路,欢迎评论分享~

在这里插入图片描述


EOF

标签:slow,删除,nums,元素,fast,数组,practise,指针
From: https://blog.csdn.net/2302_79031646/article/details/140965592

相关文章

  • 利用指针来升序数组,(冒泡排序)
    我们写完数组后,通过写函数来是代码清晰明了,第一个升序函数,通过传入arr与len,再用冒泡排序的方法即可将数组升序,这里注意,传入arr,也就是数组的首地址,函数用Int*arr接受,这里传入首地址,也就是指针的方法,这个首地址(指针)允许函数内部通过数组索引的方法来访问数组中的其他元素,......
  • 怎么彻底删除iPhone里的照片:确保你的隐私安全
    对于iPhone用户来说,照片往往记录了我们生活中的重要时刻。但在某些情况下,我们可能需要彻底删除某些照片,无论是为了释放存储空间,还是出于隐私保护的考虑。尽管在iPhone上删除照片看似简单,但许多用户可能不知道,仅仅从相册中删除照片并不能彻底清除它们。本文将指导你怎么彻底删除......
  • 栈、队列和数组有哪些主要区别
    1、数据存储和访问原则栈(Stack):存储原则:后进先出(LIFO,LastInFirstOut)。即最后加入的元素最先被移除。访问方式:只能访问栈顶元素。栈的插入(push)和删除(pop)操作都只能在栈顶进行。队列(Queue):存储原则:先进先出(FIFO,FirstInFirstOut)。即最早加入的元素最先被移除。访问方......
  • 栈、队列和数组的具体实例
    1、栈的具体实例1、自助餐厅的托盘:在自助餐厅中,托盘通常被堆叠在一起,顾客从顶部取出一个托盘,然后服务员会在底部补充一个新的托盘。这个过程体现了栈的后进先出(LIFO)特性。2、网页浏览器的历史记录:当你在网页浏览器中浏览网页时,浏览器会将你访问的网页地址保存在一个栈中......
  • 数组的概念
    数组的概念数组(Array)是一种基础且广泛使用的数据结构,用于在计算机内存中连续存储相同类型的数据。数组中的每个元素可以通过索引(或下标)进行访问,索引通常是整数,用于指定元素在数组中的位置。第一个元素的索引通常是0(但在某些编程语言中可能是1),随后的元素索引依次递增。数组的主......
  • 多维数组
    多维数组目录多维数组定义与特点特点应用场景遍历与操作注意事项定义与特点定义:多维数组是由一组类型相同的数据元素构成的有序集合,这些数据元素受多个线性关系的约束,每个线性关系对应一个维度。特点类型一致性:多维数组中的所有元素必须是相同的数据类型。连续存储:在......
  • 数组
    数组概念Java数组是一种数据结构,用于在计算机内存中连续存储相同类型的数据。数组中的每个元素可以通过索引来访问,索引通常是从0开始的。数组是Java中用于处理集合的基础,它提供了一种方式来存储和操作固定大小的同类型数据项的集合。一维数组数组的声明和创建在Java中,你可以通......
  • 在 TfidfVectorizer 标记化后删除二元组
    我正在尝试删除由TfidfVectorizer创建的二元组。我正在使用text.TfidfVectorizer,以便我可以使用自己的预处理器函数。Initfromsklearn.feature_extraction.textimportENGLISH_STOP_WORDSasstop_wordsfromsklearn.feature_extraction.textimportTfidfV......
  • 仓颉编程语言入门 -- Array数组详解
    仓颉编程语言入门–Array数组详解一.如何创建Array数组我们可以使用Array类型来构造单一元素类型,有序序列的数据。1.仓颉使用Array来表示Array类型。T表示Array的元素类型,T可以是任意类型,类似于泛型的概念vararr:Array<String>=["你好","仓颉"]va......
  • 深圳大学-电信院-C程序设计实验-数组、函数、结构体的综合使用
    实验目的(1)进一步掌握数组的定义与使用;进一步掌握函数的定义和函数调用方法;(2)学习和掌握结构体的定义和使用方法;(3)进一步掌握C语言的编程方法;学习动画程序的基本设计思想和方法。实验内容本实验编写一个在控制台窗口中,在不考虑重力的条件下,模拟一组弹球在一个二......