去除有序数组中重复元素的三种常用方法

简介: 教你如何去除有序数组中的重复元素


问题

给定一个有序数组,要删除数组重复出现的元素,使得每个元素只出现一次,然后返回移除重复数组后的新长度;

示例

假设给定一个数组 nums = [1,2,4,4],删除重复出现的元素 4 后,原数组变成 nums = [1, 2, 4],此时新的数组长度为 3;

解决思路

数组原地操作

数组原地操作,此时无需创建新的数组,只需要在原来的数组上操作即可。相当于首先要找到数组中重复的元素,然后将重复的元素移除,此时就涉及到数组中的删除操作,相关知识点可以看我的另一篇文章 数组的增删改查

这是一种时间换空间的方法,此时的空间复杂度为 O(1),时间复杂度为 O(n^2),具体实现可以参考如下代码,其中也详细注释了每一步操作。

/**

* 去除有序数组中重复元素并返回数组的新长度

* @param nums

* @return 删除重复元素后数组的新长度

*/

publicintremoveDuplicates(int[] nums) {

   // 数组初始容量

   intlength=nums.length;

   

   // 我们假定数组最后一个元素是唯一的,然后对于其他的每个元素,如果自身与它后边的数相同,那么就删除这个相同的元素

   for(inti=length-2; i>=0; i++){

       // 比较当前元素与其后一个元素是否相等

       if(nums[i] ==nums[i+1]){

           // 若相等,则移除后一位,并将所有元素向前移动一位

           for(intj=i+1; j<length; j++){

               num[j-1] =nums[j];

           }

           length--;

       }

   }

   

   // 返回数组的新长度

   returnlength;

}

普通方法

针对数组原地操作算法时间复杂度为 O(n^2),为降低时间复杂度提高算法效率,可以通过空间换时间的做法,通过定义新的数组,从而实现去除重复元素的目的,此时的时间复杂度为 O(n),而空间复杂度也由 O(1) 变成了 O(n)。但是有几点需要注意:

  1. 临界情况(即数组为空);
  2. 创建新数组时,需要指定其容量,所以需要先求出原数组中无重复元素时的元素个数;
  3. 最后则是将原数组中未重复的元素赋值给新数组;

/**

* 去除有序数组中重复元素并返回数组的新长度

* @param nums

* @return 删除重复元素后的新数组

*/

publicint[] removeDuplicates(int[] nums) {

   // 临界情况

   if(nums.length==0){

       returnnums;

   }

   

   // 先求出数组中无重复时的元素个数

   intsize=0;

   for(inti=0; i<nums.length; i++){

       if(i==0||nums[i] !=nums[i-1]){

           size++;

       }

   }

   

   // 用于存放不含重复元素的有序数组

   int[] resultArr=newint[size];

   

   intindex=0;

   for(inti=0; i<nums.length; i++){

       if(i==0||nums[i] !=nums[i+1]){

           resultArr[index++] =nums[i];

       }

   }

   

   // 返回新的不含重复元素的有序数组

   returnresultArr;    

}

双指针

以上的两种方法要么是以时间换空间,要么是以空间换时间,那我们有没有一种折中的办法,既能保证时间复杂度很低,也能保证空间复杂度呢?答案是:当然有!

利用双指针的思想,既可以将空间复杂度控制在 O(1),也可以将时间复杂度控制在 O(n)

/**

* 去除有序数组中重复元素并返回数组的新长度

* @param nums

* @return 删除重复元素后数组的新长度

*/

publicintremoveDuplicates(int[] nums) {

  // 临界情况

   if(nums.length==0){

       reutrn0;

   }

   

   intsize=0;

   for(inti=1; i<nums.length; i++){

       if(nums[size] !=nums[i]){

           nums[++size] =nums[i];


       }

   }    

   

   // 返回新长度

   returnsize+1;

}

总结

以上就是 3 种去除有序数组中重复元素的三种算法,其中既有以时间换空间的数组原地操作法,也有空间换时间的普通方法,最后的话则是有一种综合前两种方法优点的方法 - 双指针。通过双指针方法,既能保证空间复杂度为 O(1),也将时间复杂度限制在了 O(n)

想不到连简单的数组去重都有这么大的学问,我们在日常学习时,大多可能只关注于如何实现功能即可。但如果要应用到工作场景中,可能就需要考虑效率问题,此时则需要根据我们的具体需求来进行选择了。

好了,以上就是今天的内容了,如果你还有其他更好的方法,欢迎留言交流呀!


目录
相关文章
|
数据采集 JSON 数据挖掘
如何利用Python实现高效数据清洗
数据清洗是数据分析过程中不可避免的一步。在大规模数据处理任务中,手动数据清洗会耗费大量时间和资源。本文介绍了如何使用Python编写脚本来自动化数据清洗,以提高数据分析的效率。
322 3
|
机器学习/深度学习 缓存 网络安全
服务器中的conda环境
服务器中的conda环境
1309 1
|
存储 弹性计算 NoSQL
libcuckoo论文概述
本文简要阐述libcuckoo项目的两篇论文基础。如有错漏之处,欢迎指出一起讨论交流。 ## 论文1 《MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing》 这篇论文主要讲了在多线程模式下如何提升cuckoo hash table的吞吐。 ### 问题 传统hash表在并发效率上并不
2017 0
libcuckoo论文概述
|
机器学习/深度学习 安全 数据挖掘
安全地运行 Jupyter 服务
【8月更文第29天】Jupyter Notebook 是一种流行的交互式计算环境,广泛应用于数据分析、机器学习等领域。然而,随着 Jupyter 服务越来越多地被部署在网络环境中,安全问题变得日益重要。本文将介绍一些最佳实践,帮助您保护 Jupyter 服务器免受攻击和数据泄露的风险。
600 0
|
10月前
|
搜索推荐 数据挖掘 API
API接口在电商的应用及收益
本文探讨了API接口技术在电商领域的应用及其带来的收益。API接口作为连接电商平台与外部系统的桥梁,实现了高效、实时的数据交换和集成,提升了用户体验、运营效率和市场竞争力。具体应用包括库存管理、支付网关、物流跟踪、自动化业务流程、个性化推荐和精准营销等方面。通过实战案例分析,展示了亚马逊和小型电商公司如何利用API接口实现自动化管理,提高了工作效率和客户满意度。未来,API接口技术将更加注重智能化、标准化、安全性和跨界合作。
419 3
|
存储 自然语言处理 监控
FunAudioLLM大模型SenseVoice和CosyVoice测评
FunAudioLLM大模型SenseVoice和CosyVoice测评
|
10月前
|
SQL 开发框架 .NET
突破T-SQL限制:利用CLR集成扩展RDS SQL Server的功能边界
CLR集成为SQL Server提供了强大的扩展能力,突破了T-SQL的限制,极大地拓展了SQL 的应用场景,如:复杂字符串处理、高性能计算、图像处理、机器学习集成、自定义加密解密等,使开发人员能够利用 .NET Framework的丰富功能来处理复杂的数据库任务。
|
人工智能 资源调度 算法
内附原文|SIGMOD’24:百万核的智能调度,云数仓如何结合AI处理用户混合负载
论文提出的Flux通过使用AI技术将短时和长时查询解耦进行自动弹性,解决了云数据仓库的性能瓶颈,同时支持了资源按需预留。Flux优于传统的方法,查询响应时间 (RT) 最多可减少75%,资源利用率提高19.0%,成本开销降低77.8%。
内附原文|SIGMOD’24:百万核的智能调度,云数仓如何结合AI处理用户混合负载
|
存储 SQL 人工智能
为什么你的RAG不起作用?失败的主要原因和解决方案
企业在尝试使用检索增强生成(RAG)时遇到困难,因为系统效果不佳且难以优化。问题主要源于语义不协调,即任务理解与底层知识间的不一致。由于向量嵌入技术的不透明性,诊断和解决这个问题变得复杂。本文旨在揭示RAG失败的原因并提供改进策略。文章探讨了RAG的工作原理,强调了语义不协调的影响,并介绍了如何通过增加结构化数据和使用语义+相关性排名来提升RAG性能。此外,建议将AI视为工具而非完整解决方案,并提醒读者当前技术仍处早期阶段,需注意挑战。
545 0

热门文章

最新文章