专栏首页菩提树下的杨过算法练习(2)-删除有序数组/单链表中的重复项

算法练习(2)-删除有序数组/单链表中的重复项

要求:

  删除有序数组(或有序单链表)中的重复项。

示例:

  输入[1,1,2,2,3] 输出[1,2,3]

  输入a->b->b->c->c 输入a->b->c

思路:

双指针,慢指针从第1个有效元素开始,快指针从第2个有效元素开始,快指针对应的元素与慢指针对应的元素比较,如果发现相同,说明有重复,快指针向前移,如果不同,说明该元素不重复,将其复制到慢指针的后一位,同时快、慢指针均向前移,不断重复,直到结束。

图解如下:

    /**
     * 有序数组删除重复项
     * @param nums
     * @return 去重后的元素个数
     */
    public int removeDuplicates(int[] nums) {
        if (nums == null) {
            return 0;
        }
        int i = 0;
        for (int j = 1; j < nums.length; j++) {
            if (nums[i] != nums[j]) {
                i++;
                if (j - i > 0) {
                    nums[i] = nums[j];
                }
            }
        }
        return i + 1;
    }

注:j即为快指针,i为慢指针,如果每个元素都不同的情况下,比如[1,2,3],为了减少无意义的移动赋值,所以加了if(j-i)>0的判断。

上述思路,也可以适用于单链表 

注:通常会在单链表头部加一个“哑”节点来简化问题,上图中的H即为“哑”节点。跟数组不同的是,当fast到达末节点时,slow的next必须设置为空,否则如果末端的几个节点出现重复时,尾巴上的重复节点甩不掉。

    private void removeDuplicate(Node dummy) {
        //辅助行,输出整个链表
        printNode(dummy);
        Node slow = dummy.next;
        Node fast = slow.next;
        while (true) {
            if (fast.value != slow.value) {
                slow.next = fast;
                slow = slow.next;
            }
            fast = fast.next;
            if (fast == null) {
                slow.next = null;
                break;
            }
        }
        //辅助行,输出整个链表
        printNode(dummy);
    }

注:当然,如果考虑空链表(或链表只有1个元素)等边界条件,大家可以在最开始自行加一些判断,Node类的定义,可参考上一篇

扩展:如果要去重的数组,不是有序的,比如['a','a','b','a','c','c'] 这种如何去重呢?

仍然可以用双指针法,但是每次fast指针对应的元素,就必须再到慢指针之前的所有元素中,对比一次,才能知道是不是重复了。

数组:

    private int removeDuplicate2(char[] src) {
        if (src == null || src.length <= 1) {
            return 0;
        }
        //辅助行,打印日志
        System.out.println(new String(src));
        int i = 0;
        for (int j = 1; j < src.length; j++) {
            boolean found = false;
            for (int k = 0; k <= i; k++) {
                if (src[k] == src[j]) {
                    found = true;
                    break;
                }
            }
            if (!found) {
                i++;
                src[i] = src[j];
            }
        }
        //辅助行,输出最终结果
        System.out.println(new String(Arrays.copyOf(src, i + 1)));
        return i + 1;
    }

当然如果允许使用HashSet的话,也可以直接扔到Set里自动去重(面试时,如果这样回答,可能会让面试官觉得投机取巧^_^)

单链表:

    private void removeDuplicate3(Node dummy) {
        //辅助行,输出整个链表
        printNode(dummy);
        Node slow = dummy.next;
        Node fast = slow.next;
        while (true) {
            Node temp = dummy.next;
            boolean found = false;
            while (temp != null) {
                if (temp.value == fast.value) {
                    found = true;
                    break;
                }
                if (temp.next == slow.next) {
                    break;
                }
                temp = temp.next;
            }
            if (!found) {
                slow.next = fast;
                slow = slow.next;
            }
            fast = fast.next;
            if (fast == null) {
                slow.next = null;
                break;
            }
        }
        //辅助行,输出整个链表
        printNode(dummy);
    }

当然,如果考虑到java里的set集合,key不允许重复的特点,可以借助set进一步简化:

    void removeDuplicate4(Node dummy) {
        //辅助行,输出整个链表
        printNode(dummy);
        Node curr = dummy.next;
        Set<String> set = new HashSet<>();
        while (curr != null && curr.next != null) {
            set.add(curr.value);
            if (set.contains(curr.next.value)) {
                curr.next = curr.next.next;
            } else {
                curr = curr.next;
            }
        }
        //辅助行,输出整个链表
        printNode(dummy);
    }

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • freeswitch笔记(7)-放音控制

    总是报错缺少文件数据参数,另外发现一个可以让freeswitch瞬间崩溃的方法: originate user/1000 &loop_playback +2 i...

    菩提树下的杨过
  • 算法:支持重复元素的二分查找

    近几天在处理的一个项目,需要频繁对一些有序超大集合进行目标查找,二分查找算法是这类问题的最优解。但是java的Arrays.binarySearch()方法,如...

    菩提树下的杨过
  • 归一化(softmax)、信息熵、交叉熵

    机器学习中经常遇到这几个概念,用大白话解释一下: 一、归一化 把几个数量级不同的数据,放在一起比较(或者画在一个数轴上),比如:一条河的长度几千甚至上万km,与...

    菩提树下的杨过
  • AI检测即将发力:3万+疑似病例诊断,100+抗疫定点医院即将部署

    一位新冠肺炎病人的CT影像大概在300张左右,平均一个病例医生靠肉眼分析需要5-15分钟。护目镜有时受到雾气的影响,影响视力,也必须慎之又慎,既要鉴别出普通肺炎...

    博文视点Broadview
  • Cloudflare泄露用户信息长达数月:系“编程错误”导致

    Cloudflare是一家位于美国的网络安全服务商,为包括Uber(优步),Fitbit,1password等在内的众多公司提供网站安全管理,性能优化等服务。近...

    FB客服
  • 承衣钵者,西湖大学

    48岁出任副校长时,大概不会想到三年后,自己离开清华,做了“前无古人”的西湖大学的校长。

    镁客网
  • 你觉得“bat”哪家公司倒闭的话,对普通人的影响是最大的呢?

    国内互联网公司能到今天的位置离不开国内对于网络的管控,当年谷歌离开中国就是很好的案例,所以百度在国内发展成了巨无霸,不可否认国内的网络环境一定程度上成就了国内的...

    程序员互动联盟
  • 你不知道“WeCity未来城市”——八分钟了解腾讯云音视频

    继2019年央视春晚首次进行4K超高清直播,实现5G内容传输后,我们日常生活的方式也在不断被刷新。从视频通话到Web端直播,从3D、5D电影到各类VR沉浸式体感...

    WeCIty城市观
  • DeepMind开源面向对象的机器学习库Sonnet,请与TF配合服用

    李林 编译整理 量子位 报道 | 公众号 QbitAI Google旗下的英国人工智能公司DeepMind今天宣布开源神经网络库Sonnet,该库使用了类似To...

    量子位
  • python 遍历文件夹 查找大文件

    import os path = "C:/" #文件夹目录 def eachFile(filepath): fileNames = os.listdir(...

    用户5760343

扫码关注云+社区

领取腾讯云代金券