专栏首页村雨遥我是如何给有序数组去重的?

我是如何给有序数组去重的?

问题

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

示例

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

解决思路

数组原地操作

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

这是一种时间换空间的方法,此时的空间复杂度为

O(1)

,时间复杂度为

O(n^2)

,具体实现可以参考如下代码,其中也详细注释了每一步操作。

/**
* 去除有序数组中重复元素并返回数组的新长度
* @param nums
* @return 删除重复元素后数组的新长度
*/
public int removeDuplicates(int[] nums) {
    // 数组初始容量
    int length = nums.length;

    // 我们假定数组最后一个元素是唯一的,然后对于其他的每个元素,如果自身与它后边的数相同,那么就删除这个相同的元素
    for(int i = length - 2; i >= 0; i++){
        // 比较当前元素与其后一个元素是否相等
        if(nums[i] == nums[i + 1]){
            // 若相等,则移除后一位,并将所有元素向前移动一位
            for(int j = i + 1; j < length; j++){
                num[j - 1] = nums[j];
            }
            length--;
        }
    }

    // 返回数组的新长度
    return length;
}

普通方法

针对数组原地操作算法时间复杂度为

O(n^2)

,为降低时间复杂度提高算法效率,可以通过空间换时间的做法,通过定义新的数组,从而实现去除重复元素的目的,此时的时间复杂度为

O(n)

,而空间复杂度也由

O(1)

变成了

O(n)

。但是有几点需要注意:

  1. 临界情况(即数组为空);
  2. 创建新数组时,需要指定其容量,所以需要先求出原数组中无重复元素时的元素个数;
  3. 最后则是将原数组中未重复的元素赋值给新数组;
/**
* 去除有序数组中重复元素并返回数组的新长度
* @param nums
* @return 删除重复元素后的新数组
*/
public int[] removeDuplicates(int[] nums) {
    // 临界情况
    if(nums.length == 0){
        return nums;
    }

    // 先求出数组中无重复时的元素个数
    int size = 0;
    for(int i = 0; i < nums.length; i++){
        if(i == 0 || nums[i] != nums[i - 1]){
            size++;
        }
    }

    // 用于存放不含重复元素的有序数组
    int[] resultArr = new int[size];

    int index = 0;
    for(int i = 0; i < nums.length; i++){
        if(i == 0 || nums[i] != nums[i + 1]){
            resultArr[index++] = nums[i];
        }
    }

    // 返回新的不含重复元素的有序数组
    return resultArr;
}

双指针

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

利用双指针的思想,既可以将空间复杂度控制在

O(1)

,也可以将时间复杂度控制在

O(n)

/**
* 去除有序数组中重复元素并返回数组的新长度
* @param nums
* @return 删除重复元素后数组的新长度
*/
public int removeDuplicates(int[] nums) {
  // 临界情况
    if(nums.length == 0){
        reutrn 0;
    }

    int size = 0;
    for(int i = 1; i < nums.length; i++){
        if(nums[size] != nums[i]){
            nums[++size] = nums[i];

        }
    }

    // 返回新长度
    return size + 1;
}

总结

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

O(1)

,也将时间复杂度限制在了

O(n)

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

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

本文分享自微信公众号 - 村雨遥(cunyu1943),作者:村雨遥

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-05-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 如何高效对有序数组/链表去重?

    我们知道对于数组来说,在尾部插入、删除元素是比较高效的,时间复杂度是 O(1),但是如果在中间或者开头插入、删除元素,就会涉及数据的搬移,时间复杂度为 O(N)...

    五分钟学算法
  • Leetcode|快慢指针助力有序数组去重|26/80. 删除有序数组中的重复项I/II

    SL_World
  • 【前端芝士树】如何完成数组的去重 Array Unique?

    CloudCat
  • 谁再问我如何写出没有Bug的代码,我上去就是一jio!

    1947 年 9 月 9 日,美国海军准将 Grace Hopper 在哈佛学院计算机实验室里使用 MarkII 和 MarkIII 计算机进行研究工作。她的团...

    Guide哥
  • 漫画:如何求两个数组的交集?如果两个数组是有序的呢? (修订版)

    设定两个为0的指针,比较两个指针的元素是否相等。如果指针的元素相等,我们将两个指针一起向前移动,并且将相等的元素放入空白数组。

    程序员小浩
  • 两个数组的交集?如果两个数组是有序的呢?

    设定两个为0的指针,比较两个指针的元素是否相等。如果指针的元素相等,我们将两个指针一起向前移动,并且将相等的元素放入空白数组。

    帅地
  • 如何答一道惊艳面试官的数组去重问题?

    思想: 双重 for 循环是比较笨拙的方法,它实现的原理很简单:先定义一个包含原始数组第一个元素的数组,然后遍历原始数组,将原始数组中的每个元素与新数组中的每个...

    coder_koala
  • 美团一面:两个有序的数组,如何高效合并成一个有序数组?

    归并算法采取思想是分治思想,分治思想简单说就是分而治之,将一个大问题分解为小问题,将小问题解答后合并为大问题的答案。

    Java技术栈
  • LeetCode 80,不使用外部空间的情况下对有序数组去重

    今天是LeetCode专题的第49篇文章,我们一起来看LeetCode的第80题,有序数组去重II(Remove Duplicates from Sorted ...

    TechFlow-承志
  • 去除有序数组中重复元素的 3 种方法,快来瞧瞧吧

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

    村雨遥
  • Confluence 6 如何让我的小组成员知道那些内容是重要的

    如果你的 Confluence 中已经有了很多内容,定义那些内容是重要看起是一件艰巨的任务 —— 但是下面的一些特性能够帮助你的小组确定那些内容是他们应该关心的...

    HoneyMoose
  • JS数组去重的6种算法实现以上就是为大家提供的6种JS数组去重的算法实现,希望对大家的学习有所帮助。

    王小婷
  • 再有人问你MySQL是如何查询数据的,请把这篇文章甩给他!

    上一篇我们说到了关于MySQL的索引的原理,主要说的是 MySQL 对于索引的字段是怎么去维护的,我们再来简单的回顾下:

    捡田螺的小男孩
  • 2020-11-11:手写代码:如何获得有序数组中指定元素的个数?

    2.二分法。二分查找元素,然后二分查找左边界,再查找右边界,最后右边界减去左边界就是指定元素个数。这道题实际上是如下三道题的综合。

    福大大架构师每日一题
  • 【MySQL】面试官问我:MySQL如何实现无数据插入,有数据更新?我是这样回答的!

    作者个人研发的在高并发场景下,提供的简单、稳定、可扩展的延迟消息队列框架,具有精准的定时任务和延迟队列处理功能。自开源半年多以来,已成功为十几家中小型企业提供了...

    冰河
  • 2021-05-12:给定一个数组arr,只能对arr中的一个子数组排序, 但是想让arr整体都有序。返回满足这一设定的子数组中

    2021-05-12:给定一个数组arr,只能对arr中的一个子数组排序, 但是想让arr整体都有序。返回满足这一设定的子数组中,最短的是多长?

    福大大架构师每日一题
  • 我的职业是前端工程师【六】:前端程序员如何有效地提高自己

    要成为一个优秀的前端工程师,需要什么技能和学习?答案:练习 在逛知乎、SegmentFault 又或者是相似的技术社区,我们总会看到类似的问题。新手总会关注于,...

    Phodal
  • 如何给新来的师妹解释什么是数据库的脏读、不可重复读和幻读

    十一国庆长假,朋友圈的朋友已经走向了大江南北,而我却在公司加班。这时候,组内新来的萌妹实习生过来找我。

    帅地
  • 一个野生程序员的真实自述:我是如何从数学专业学渣入坑程序员的

    本文来自公众号“程序员loading”,原标题是“排除万难,我终于入了程序员的坑!”。

    JackJiang

扫码关注云+社区

领取腾讯云代金券