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

麦洛 等级 1083 0 0
标签: Java

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

大家好,今天我们来研究一个比较常见的编码问题。 假如现在给我们一个对象数组,它可以是整数数组和字符串数组,也可以是实现 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),同时也展示了利用泛型实现方法的通用性;

收藏
评论区

相关推荐

阿里程序员的Java之路!2021年最新Java面试点梳理
面试题模块介绍: 一、Java 基础 JDK 和 JRE 有什么区别? 和 equals 的区别是什么? 两个对象的 hashCode()相同,则 equals()也一定为 true,对吗? final 在 java 中有什么作用? java 中的 Math.round(1.5) 等于多少? String 属于基础的数据类型吗?
腾讯T3团队整理,持续更新中
Java基础1.JAVA 中的几种数据类型是什么,各自占用多少字节。2.String 类能被继承吗,为什么。3\. 两个对象的 hashCode() 相同,则 equals() 也一定为 true,对吗?4\. String 属于基础的数据类型吗?5.Java 中操作字符串都有哪些类?它们之间有什么区别?6.Java 中 IO 流分为几种?7.BIO、NIO
为什么说Python是最伟大的语言?看图就知道了!
测试一下你的分析能力,直接上图,自己判断一下为什么Python是最好的语言?有图有真相 Java之父 James Goshling C++之父 Bjarne Stroustrup PHP之父 Rasmus Lerdorf Python之父 Guido van Rossum看到他们的亮点了吗? Java和C++是锃亮的电灯泡 PHP是一
C++ 为什么不加入垃圾回收机制
> 来源:M-先生 > > 链接:http://blog.csdn.net/yeahhook/article/details/6796242 Java的爱好者们经常批评C++中没有提供与Java类似的垃圾回收(Gabage Collector)机制(这很正常,正如C++的爱好者有时也攻击Java没有这个没有那个,或者这个不行那个不够好),导致C++中对动
JDK 16 新特性,正式发布!程序员:追不上了...
![](https://oscimg.oschina.net/oscnet/cc3506e3-116b-4599-8cb5-5c007a050285.jpg) **地址:https://blog.csdn.net/csdnnews/article/details/110483909** **没错,是的,JDK 16 新特性,先来了** > 你还能追
Java 中初始化 List 集合的 6 种方式!
![](https://oscimg.oschina.net/oscnet/0db5449d0736e22cb92ba0cf9daad91990a.jpg)   List 是 Java 开发中经常会使用的集合,你们知道有哪些方式可以初始化一个 List 吗?这其中不缺乏一些坑,今天栈长我给大家一一普及一下。   1、常规方式   ListString
Java 中初始化 List 集合的 6 种方式!
![](https://oscimg.oschina.net/oscnet/26618d87-ed40-4f14-b290-16a3e22e57fe.png) List 是 Java 开发中经常会使用的集合,你们知道有哪些方式可以初始化一个 List 吗?这其中不缺乏一些坑,今天栈长我给大家一一普及一下。 1、常规方式 ------ Lis
Java中的常用异常处理方法
觉得自己是一个Java专家吗?是否肯定自己已经全面掌握了Java的异常处理机制?在下面这段代码中,你能够迅速找出异常处理的六个问题吗? 1 OutputStreamWriter out = ... 2 java.sql.Connection conn = ... 3 try { // ⑸ 4  Statement stat = conn.createSta
Java中的深浅拷贝问题你清楚吗?
**一、前言** 拷贝这个词想必大家都很熟悉,在工作中经常需要拷贝一份文件作为副本。拷贝的好处也很明显,相较于新建来说,可以节省很大的工作量。在Java中,同样存在拷贝这个概念,拷贝的意义也是可以节省创建对象的开销。 `Object`类中有一个方法`clone()`,具体方法如下: protected native Object clone()
Java多线程带返回值的Callable接口
Java多线程带返回值的Callable接口 在面试的时候,有时候是不是会遇到面试会问你,Java中实现多线程的方式有几种?你知道吗?你知道Java中有可以返回值的线程吗?在具体的用法你知道吗?如果两个线程同时来调用同一个计算对象,计算对象的call方法会被调用几次你知道吗?如果这些你知道,那么凯哥(凯哥Java:kaigejava)恭喜你,本文你可以不用
Java大佬精心为小白整理的十个学习心德
零基础学习 java 能学会吗? 零基础如何学习 java? 有什么方法吗? 今天由我来分享下关于零基础学习 java 的方法。 Java发展前景 -------- 据权威统计,在所有软件开发类人才的需求中,对 Java 工程师的需求达到全部需求量的 60%~70%,Java 软件人才的缺口巨大,对应薪水也是随之水涨船高。 越来越多的大学生看好
Java:类与继承
  对于面向对象的程序设计语言来说,类毫无疑问是其最重要的基础。抽象、封装、继承、多态这四大特性都离不开类,只有存在类,才能体现面向对象编程的特点,今天我们就来了解一些类与继承的相关知识。首先,我们讲述一下与类的初始化相关的东西,然后再从几个方面阐述继承这一大特性。以下是本文的目录大纲:   一.你了解类吗?   二.你了解继承吗?   三.常见的面试
java这个404你能解决吗?
今天在tomcat里部署运行了一个小工程,工程结构如下: ![在这里插入图片描述](https://oscimg.oschina.net/oscnet/7db247c54629e3e2a1aa79e3fa69e131780.png) 运行tomcat服务器后,访问index.html,发现报404: ![在这里插入图片描述](https://oscimg
java面试题汇总,不断更新中。。。
**JVM,并发,锁相关:** 1.请你谈谈对volatile的理解,volatile是否存在伪共享问题。 2.cas你知道吗? 3.原子类AtomicInteger的ABA问题谈谈?原子更新引用知道吗? 4.公平锁/非公平锁/可重入锁/递归锁/自旋锁谈谈你的理解?请手写一个自旋锁。 5.CountDownLatch、CyclicBarrier、S
Spring Boot 最核心的 3 个注解详解
最近面试一些 Java 开发者,他们其中有些在公司实际用过 Spring Boot, 有些是自己兴趣爱好在业余自己学习过。然而,当我问他们 Spring Boot 最核心的 3 个注解是什么,令我失望的是鲜有人能答上来,这样你能说你对 Spring Boot 很了解吗?这可能还会给你减分! 你所需具备的基础 -------- * [什么是 Sprin