java中删除数组中重复元素方法探讨

作者：isme7 | 来源：互联网 | 2022-03-02 22:48

这个是一个老问题，但是发现大多数人说的还不够透。小弟就在这里抛砖引玉了，欢迎拍砖

问题：比如我有一个数组（元素个数为0哈），希望添加进去元素不能重复。

　　拿到这样一个问题，我可能会快速的写下代码，这里数组用ArrayList.

代码如下:

private static void testListSet(){
        List arrays = new ArrayList(){
            @Override
            public boolean add(String e) {
                for(String str:this){
                    if(str.equals(e)){
                        System.out.println("add failed !!!  duplicate element");
                        return false;
                    }else{
                        System.out.println("add successed !!!");
                    }
                }
                return super.add(e);
            }
        };

        arrays.add("a");arrays.add("b");arrays.add("c");arrays.add("b");
        for(String e:arrays)
            System.out.print(e);
    }

这里我什么都不关，只关心在数组添加元素的时候做下判断（当然添加数组元素只用add方法），是否已存在相同元素，如果数组中不存在这个元素，就添加到这个数组中，反之亦然。这样写可能简单，但是面临庞大数组时就显得笨拙：有100000元素的数组天家一个元素，难道要调用100000次equal吗？这里是个基础。

问题：加入已经有一些元素的数组了，怎么删除这个数组里重复的元素呢？

　　大家知道java中集合总的可以分为两大类：List与Set。List类的集合里元素要求有序但可以重复，而Set类的集合里元素要求无序但不能重复。那么这里就可以考虑利用Set这个特性把重复元素删除不就达到目的了，毕竟用系统里已有的算法要优于自己现写的算法吧。

代码如下:

public static void removeDuplicate(List list){
       HashSet set = new HashSet(list);
       list.clear();
       list.addAll(set);
    }　　private static People[] ObjData = new People[]{
        new People(0, "a"),new People(1, "b"),new People(0, "a"),new People(2, "a"),new People(3, "c"),
    };　

代码如下:

public class People{
    private int id;
    private String name;

    public People(int id,String name){
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return ("id = "+id+" , name "+name);
    }    
}

上面的代码，用了一个自定义的People类，当我添加相同的对象时候（指的是含有相同的数据内容），调用removeDuplicate方法发现这样并不能解决实际问题，仍然存在相同的对象。那么HashSet里是怎么判断像个对象是否相同的呢？打开HashSet源码可以发现：每次往里面添加数据的时候，就必须要调用add方法：

代码如下:

@Override 
     public boolean add(E object) { 
         return backingMap.put(object, this) == null; 
     }

这里的backingMap也就是HashSet维护的数据，它用了一个很巧妙的方法，把每次添加的Object当作HashMap里面的KEY，本身HashSet对象当作VALUE。这样就利用了Hashmap里的KEY唯一性，自然而然的HashSet的数据不会重复。但是真正的是否有重复数据，就得看HashMap里的怎么判断两个KEY是否相同。

代码如下:

@Override public V put(K key, V value) {
        if (key == null) {
            return putValueForNullKey(value);
        }

        int hash = secondaryHash(key.hashCode());
        HashMapEntry[] tab = table;
        int index = hash & (tab.length - 1);
        for (HashMapEntry e = tab[index]; e != null; e = e.next) {
            if (e.hash == hash && key.equals(e.key)) {
                preModify(e);
                V oldValue = e.value;
                e.value = value;
                return oldValue;
            }
        }

        // No entry for (non-null) key is present; create one
        modCount++;
        if (size++ > threshold) {
            tab = doubleCapacity();
            index = hash & (tab.length - 1);
        }
        addNewEntry(key, value, hash, index);
        return null;
    }

总的来说，这里实现的思路是：遍历hashmap里的元素，如果元素的hashcode相等（事实上还要对hashcode做一次处理），然后去判断KEY的eqaul方法。如果这两个条件满足，那么就是不同元素。那这里如果数组里的元素类型是自定义的话，要利用Set的机制，那就得自己实现equal与hashmap（这里hashmap算法就不详细介绍了，我也就理解一点）方法了：

代码如下:

public class People{
    private int id; //
    private String name;

    public People(int id,String name){
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return ("id = "+id+" , name "+name);
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    @Override
    public boolean equals(Object obj) {
        if(!(obj instanceof People))
            return false;
        People o = (People)obj;
        if(id == o.getId()&&name.equals(o.getName()))
            return true;
        else
            return false;
    }

    @Override
    public int hashCode() {
        // TODO Auto-generated method stub
        return id;
        //return super.hashCode();
    }
}

这里在调用removeDuplicate(list)方法就不会出现两个相同的people了。

好吧，这里就测试它们的性能吧：

代码如下:

public class RemoveDeplicate {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        //testListSet();
        //removeDuplicateWithOrder(Arrays.asList(data));
        //ArrayList list = new ArrayList(Arrays.asList(ObjData));

        //removeDuplicate(list);

        People[] data = createObjectArray(10000);
        ArrayList list = new ArrayList(Arrays.asList(data));

        long startTime1 = System.currentTimeMillis();
        System.out.println("set start time --> "+startTime1);
        removeDuplicate(list);
        long endTime1 = System.currentTimeMillis();
        System.out.println("set end time --> "+endTime1);
        System.out.println("set total time --> "+(endTime1-startTime1));
        System.out.println("count : " + People.count);
        People.count = 0;

        long startTime = System.currentTimeMillis();
        System.out.println("Efficient start time --> "+startTime);
        EfficientRemoveDup(data);
        long endTime = System.currentTimeMillis();
        System.out.println("Efficient end time --> "+endTime);
        System.out.println("Efficient total time --> "+(endTime-startTime));
        System.out.println("count : " + People.count);

    }
    public static void removeDuplicate(List list)
    {
     HashSet set = new HashSet(list);
     list.clear();
     list.addAll(set);
    }

    public static void removeDuplicateWithOrder(List arlList)
    {
       Set set = new HashSet();
       List newList = new ArrayList();
       for (Iterator iter = arlList.iterator(); iter.hasNext();) {
          String element = iter.next();
          if (set.add( element))
             newList.add( element);
       }
       arlList.clear();
       arlList.addAll(newList);
    }


    @SuppressWarnings("serial")
    private static void testListSet(){
        List arrays = new ArrayList(){
            @Override
            public boolean add(String e) {
                for(String str:this){
                    if(str.equals(e)){
                        System.out.println("add failed !!! duplicate element");
                        return false;
                    }else{
                        System.out.println("add successed !!!");
                    }
                }
                return super.add(e);
            }
        };

        arrays.add("a");arrays.add("b");arrays.add("c");arrays.add("b");
        for(String e:arrays)
            System.out.print(e);
    }

    private static void EfficientRemoveDup(People[] peoples){
        //Object[] originalArray; // again, pretend this contains our original data
        int count =0;
        // new temporary array to hold non-duplicate data
        People[] newArray = new People[peoples.length];
        // current index in the new array (also the number of non-dup elements)
        int currentIndex = 0;

        // loop through the original array...
        for (int i = 0; i             // cOntains=> true iff newArray contains originalArray[i]
            boolean cOntains= false;

            // search through newArray to see if it contains an element equal
            // to the element in originalArray[i]
            for(int j = 0; j <= currentIndex; ++j) {
                // if the same element is found, don't add it to the new array
                count++;
                if(peoples[i].equals(newArray[j])) {

                    cOntains= true;
                    break;
                }
            }

            // if we didn't find a duplicate, add the new element to the new array
            if(!contains) {
                // note: you may want to use a copy constructor, or a .clone()
                // here if the situation warrants more than a shallow copy
                newArray[currentIndex] = peoples[i];
                ++currentIndex;
            }
        }

        System.out.println("efficient medthod inner count : "+ count);

    }

    private static People[] createObjectArray(int length){
        int num = length;
        People[] data = new People[num];
        Random random = new Random();
        for(int i = 0;i            int id = random.nextInt(10000);
            System.out.print(id + " ");
            data[i]=new People(id, "i am a man");
        }
        return data;
    }
｝

测试结果：

代码如下:

set end time -->  1326443326724
set total time -->  26
count : 3653
Efficient start time --> 1326443326729
efficient medthod inner  count : 28463252
Efficient end time -->  1326443327107
Efficient total time -->  378
count : 28463252

算法

推荐阅读

算法
JavaScript疑难杂症系列相称性推断的知识点详解

本文详细解析了JavaScript中相称性推断的知识点，包括严厉相称和宽松相称的区别，以及范例转换的规则。针对不同类型的范例值，如差别范例值、统一类的原始范例值和统一类的复合范例值，都给出了具体的比较方法。对于宽松相称的情况，也解释了原始范例值和对象之间的比较规则。通过本文的学习，读者可以更好地理解JavaScript中相称性推断的概念和应用。 ... [详细]

蜡笔小新 2023-12-14 19:12:10
算法
每天收获一点点Hadoop概述

一、Hadoop来历Hadoop的思想来源于Google在做搜索引擎的时候出现一个很大的问题就是这么多网页我如何才能以最快的速度来搜索到，由于这个问题Google发明 ... [详细]

蜡笔小新 2023-12-14 18:58:01
算法
Android中高级面试必知必会，积累总结

本文介绍了Android中高级面试的必知必会内容，并总结了相关经验。文章指出，如今的Android市场对开发人员的要求更高，需要更专业的人才。同时，文章还给出了针对Android岗位的职责和要求，并提供了简历突出的建议。 ... [详细]

蜡笔小新 2023-12-14 14:53:02
算法
CSS3选择器的使用方法详解，提高Web开发效率和精准度

本文详细介绍了CSS3新增的选择器方法，包括属性选择器的使用。通过CSS3选择器，可以提高Web开发的效率和精准度，使得查找元素更加方便和快捷。同时，本文还对属性选择器的各种用法进行了详细解释，并给出了相应的代码示例。通过学习本文，读者可以更好地掌握CSS3选择器的使用方法，提升自己的Web开发能力。 ... [详细]

蜡笔小新 2023-12-14 14:37:52
算法
Java工具类库Hutool介绍及功能概述

本文介绍了Java工具类库Hutool，该工具包封装了对文件、流、加密解密、转码、正则、线程、XML等JDK方法的封装，并提供了各种Util工具类。同时，还介绍了Hutool的组件，包括动态代理、布隆过滤、缓存、定时任务等功能。该工具包可以简化Java代码，提高开发效率。 ... [详细]

蜡笔小新 2023-12-14 14:29:36
算法
C#生成随机数的三种方法及其问题分析

本文介绍了C#中生成随机数的三种方法，并分析了其中存在的问题。首先介绍了使用Random类生成随机数的默认方法，但在高并发情况下可能会出现重复的情况。接着通过循环生成了一系列随机数，进一步突显了这个问题。文章指出，随机数生成在任何编程语言中都是必备的功能，但Random类生成的随机数并不可靠。最后，提出了需要寻找其他可靠的随机数生成方法的建议。 ... [详细]

蜡笔小新 2023-12-14 14:15:30
算法
qt学习(六)数据库注册用户的实现方法

本文介绍了在qt学习中实现数据库注册用户的方法，包括登录按钮按下后出现注册页面、账号可用性判断、密码格式判断、邮箱格式判断等步骤。具体实现过程包括UI设计、数据库的创建和各个模块调用数据内容。 ... [详细]

蜡笔小新 2023-12-14 13:29:32
自动驾驶
2020年AI产业报告：100个岗位抢1个人，计算机视觉成最大缺口

“你永远都不知道明天和‘公司的意外’哪个先来。”疫情期间，这是我们最战战兢兢的心情。但是显然，有些人体会不了。这份行业数据，让笔者“柠檬” ... [详细]

蜡笔小新 2023-12-14 12:23:22
算法
生成对抗式网络GAN及其衍生CGAN、DCGAN、WGAN、LSGAN、BEGAN介绍

一、GAN原理介绍学习GAN的第一篇论文当然由是IanGoodfellow于2014年发表的GenerativeAdversarialNetworks（论文下载链接arxiv：[h ... [详细]

蜡笔小新 2023-12-14 11:39:45
人脸识别
[译]技术公司十年经验的职场生涯回顾

本文是一位在技术公司工作十年的职场人士对自己职业生涯的总结回顾。她的职业规划与众不同，令人深思又有趣。其中涉及到的内容有机器学习、创新创业以及引用了女性主义者在TED演讲中的部分讲义。文章表达了对职业生涯的愿望和希望，认为人类有能力不断改善自己。 ... [详细]

蜡笔小新 2023-12-14 11:31:05
算法
无线认证设置故障排除方法及注意事项

本文介绍了解决无线认证设置故障的方法和注意事项，包括检查无线路由器工作状态、关闭手机休眠状态下的网络设置、重启路由器、更改认证类型、恢复出厂设置和手机网络设置等。通过这些方法，可以解决无线认证设置可能出现的问题，确保无线网络正常连接和上网。同时，还提供了一些注意事项，以便用户在进行无线认证设置时能够正确操作。 ... [详细]

蜡笔小新 2023-12-14 10:32:21
算法
游戏开发中的人工智能技术及分类介绍

本文介绍了游戏开发中的人工智能技术，包括定性行为和非定性行为的分类。定性行为是指特定且可预测的行为，而非定性行为则具有一定程度的不确定性。其中，追逐算法是定性行为的具体实例。 ... [详细]

蜡笔小新 2023-12-14 10:22:59
算法
JavaScript设计模式之策略模式（Strategy Pattern）的优势及应用

本文介绍了JavaScript设计模式之策略模式（Strategy Pattern）的定义和优势，策略模式可以避免代码中的多重判断条件，体现了开放-封闭原则。同时，策略模式的应用可以使系统的算法重复利用，避免复制粘贴。然而，策略模式也会增加策略类的数量，违反最少知识原则，需要了解各种策略类才能更好地应用于业务中。本文还以员工年终奖的计算为例，说明了策略模式的应用场景和实现方式。 ... [详细]

蜡笔小新 2023-12-14 09:31:45
算法
PhysioNet生理信号处理（三）WFDB Toolbox for Matlab的安装和使用方法

本文介绍了PhysioNet网站提供的生理信号处理工具箱WFDB Toolbox for Matlab的安装和使用方法。通过下载并添加到Matlab路径中或直接在Matlab中输入相关内容，即可完成安装。该工具箱提供了一系列函数，可以方便地处理生理信号数据。详细的安装和使用方法可以参考本文内容。 ... [详细]

蜡笔小新 2023-12-13 20:46:48
算法
相机防抖设置详解及使用方法

本文详细介绍了相机防抖的设置方法和使用技巧，包括索尼防抖设置、VR和Stabilizer档位的选择、机身菜单设置等。同时解释了相机防抖的原理，包括电子防抖和光学防抖的区别，以及它们对画质细节的影响。此外，还提到了一些运动相机的防抖方法，如大疆的Osmo Action的Rock Steady技术。通过本文，你将更好地理解相机防抖的重要性和使用技巧，提高拍摄体验。 ... [详细]

蜡笔小新 2023-12-13 20:39:20

isme7

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章