过滤数组中重复元素,你知道最优方案吗?

爱写Bug的麦洛
• 阅读 1548

过滤数组中重复元素,你知道最优方案吗?

大家好,今天我们来研究一个比较常见的编码问题。 假如现在给我们一个对象数组,它可以是整数数组和字符串数组,也可以是实现 Comparable 接口的任何对象。

带着以下问题,我们来开始今天的文章:

  • 我们如何从数组中找到重复的元素?
  • 你能用 O(n) 复杂度来解决这个问题吗?

不论在日常工作中,或者在面试中,这都是经常遇到的问题;

其实有多种方法可以解决这个问题,在这里我们将讨论两种比较常见的方法,首先是常规方法,这种方法指将每个元素与其他元素进行比较,其次是使用类似哈希表的数据结构来将问题的时间复杂度从二次降低到线性,当然要增加一些空间复杂度。这也说明通过使用合理的数据结构,我们可以想出更优时间复杂度的算法来解决问题,所以说数据结构和算法的相关知识对程序员非常重要;

方案1- 在 O(n^2)中寻找重复项

在第一种解决方案中,我们将数组中的每个元素与其他每个元素进行比较。 如果它们相同,那么就有重复项,如果不相同,那么就没有重复项,通常把这种方法称为:暴力破解算法

当我们使用这种方案从数组中寻找重复项时,它的时间复杂度就是O (n ^ 2)

    public static Set<Integer> findDuplicates(int[] input) {
        Set<Integer> duplicates = new HashSet<Integer>();

        for (int i = 0; i < input.length; i++) {
            for (int j = 1; j < input.length; j++) {
                if (input[i] == input[j] && i != j) {
                    // duplicate element found
                    duplicates.add(input[i]);
                    break;
                }
            }
        }

        return duplicates;
    }

我们将最后的重复项放入到Set集合返回,但是如果面试官问你还有其他优化方案吗?将它的时间复杂度降为O(n);

我们接着往下看

方案2 - 在 O(n) 中寻找重复项

第二个解决方案演示了如何使用合适的数据结构编写更好的算法来解决同样的问题。 我们知道,在 Java 中,由于Set 集合底层是基于散列表数据结构所以不允许重复元素,因此平均情况下插入需要 O(1)

通过HashSet集合来解决这个问题,我们可以在O(n)时间内完成,我们在for循环中将每个元素插入HashSet中,因为它只允许唯一的元素,所以当我们尝试添加重复元素时候,add()方法会返回false;

最后,我们将重复下打印出来,看看是不是可以实现我们的需求;

public static <T extends Comparable<T>> void getDuplicates(T[] array) {
        Set<T> dupes = new HashSet<T>();
        for (T i : array) {
            if (!dupes.add(i)) {
                System.out.println("Duplicate element in array is : " + i);
            }
        }

    }

这个方法适用于Java中任何类型的 Java 数组,比如 Array with IntegerArray with String 或者任何实现 Comparable 接口的对象,但是不适用于原语数组,因为它们在 Java 中不是对象

代码清单

为了方便大家测试,提供了代码清单,大家可以直接跑一跑

package com.milo.collection.list;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 过滤数组中重复的元素
 * @author milogenius
 * @date 2020/4/22 23:03
 */
public class DuplicatesFromArray {
    public static void main(String args[]) {
        int[] withDuplicates = { 1, 2, 3, 1, 2, 3, 4, 5, 3, 6 };
        //调用常规方法
        Set<Integer> duplicates = findDuplicates(withDuplicates);
        System.out.println("input array is : " + Arrays.toString(withDuplicates));
        System.out.println("Duplicate elements found in array are : " + duplicates);

        // 调用泛型方法
        String[] myArray = { "ab", "cd", "ab", "de", "cd" };
        System.out.println("input string array is : " + Arrays.toString(myArray));
        getDuplicates(myArray);
    }

    /**
     * 时间复杂度是O(n²)
     *
     * @param input
     * @return
     */
    public static Set<Integer> findDuplicates(int[] input) {
        Set<Integer> duplicates = new HashSet<Integer>();

        for (int i = 0; i < input.length; i++) {
            for (int j = 1; j < input.length; j++) {
                if (input[i] == input[j] && i != j) {
                    // 发现重复元素
                    duplicates.add(input[i]);
                    break;
                }
            }
        }

        return duplicates;
    }

    /**
     * 时间复杂度为O(n) ,因为我们使用了HashSet数据结构
     *
     * @param array
     * @return
     */
    public static <T extends Comparable<T>> void getDuplicates(T[] array) {
        Set<T> dupes = new HashSet<T>();
        for (T i : array) {
            if (!dupes.add(i)) {
                System.out.println("Duplicate element in array is : " + i);
            }
        }

    }


}


Output :
input array is : [1, 2, 3, 1, 2, 3, 4, 5, 3, 6]
Duplicate elements found in array are : [1, 2, 3]
input string array is : [ab, cd, ab, de, cd]
Duplicate element in array is : ab
Duplicate element in array is : cd

总结

我们学习了两种解决如何在数组中找到重复元素的方法,第一个解决方案是暴力破解算法,第二个解决方案是我们使用HashSet数据结构将第一种方案的时间复杂度从O(n^2)降为O (n),同时也展示了利用泛型实现方法的通用性;

点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Wesley13 Wesley13
3年前
java将前端的json数组字符串转换为列表
记录下在前端通过ajax提交了一个json数组的字符串,在后端如何转换为列表。前端数据转化与请求varcontracts{id:'1',name:'yanggb合同1'},{id:'2',name:'yanggb合同2'},{id:'3',name:'yang
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
3个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Wesley13 Wesley13
3年前
Java开发者容易犯的十个错误
!(https://oscimg.oschina.net/oscnet/c9f00cc918684fbe8a865119d104090b.gif)Top1.数组转换为数组列表将数组转换为数组列表,开发者经常会这样做:\java\List<StringlistArrays.asList(arr);Arr
Stella981 Stella981
3年前
JS 对象数组Array 根据对象object key的值排序sort,很风骚哦
有个js对象数组varary\{id:1,name:"b"},{id:2,name:"b"}\需求是根据name或者id的值来排序,这里有个风骚的函数函数定义:function keysrt(key,desc) {  return function(a,b){    return desc ? ~~(ak
Wesley13 Wesley13
3年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Wesley13 Wesley13
3年前
ES6 新增的数组的方法
给定一个数组letlist\//wu:武力zhi:智力{id:1,name:'张飞',wu:97,zhi:10},{id:2,name:'诸葛亮',wu:55,zhi:99},{id:3,name:'赵云',wu:97,zhi:66},{id:4,na
Wesley13 Wesley13
3年前
35岁是技术人的天花板吗?
35岁是技术人的天花板吗?我非常不认同“35岁现象”,人类没有那么脆弱,人类的智力不会说是35岁之后就停止发展,更不是说35岁之后就没有机会了。马云35岁还在教书,任正非35岁还在工厂上班。为什么技术人员到35岁就应该退役了呢?所以35岁根本就不是一个问题,我今年已经37岁了,我发现我才刚刚找到自己的节奏,刚刚上路。
达里尔 达里尔
10个月前
给数组添加新数据,判断数据是否重复
多选要进行数组拼接,希望判断往原数组里添的新数据是否重复,封装个简易方法languageconstdataArrayname:'aaa',id:1,name:'bbb',id:2;constnewDataname:'ccc',id:2;//要添加的新数