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

麦洛 等级 653 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),同时也展示了利用泛型实现方法的通用性;

收藏
评论区

相关推荐

过滤数组中重复元素,你知道最优方案吗?
大家好,今天我们来研究一个比较常见的编码问题。 假如现在给我们一个对象数组,它可以是整数数组和字符串数组,也可以是实现 Comparable 接口的任何
初学者 对于 入坑程序员的一些看法
程序员 工资高? 是的 确实是 那你入坑之前有没有想过这个前提呢? 你查一查什么职位高 例如 Java 架构师 那你想想 什么才叫架构师 什么程度 要这么学习 才能达到这个程度? 了解过编程达到什么程度 才可以达到工资高吗 你大概是不知道的 那从另一个概念想想: 程序员 秃顶的形象大家都应该做到的; 为什么会秃顶? 秃顶的都
java传值和传引用问题
这个问题还是很常见的,如果你平常敲代码比较多你可能经常会遇到这个问题。如果你知道java这个机制,你可能还会一直在找代码的问题。java中的值传递和引用传递。比如下面有这俩个方法java private void updataValue(String s){ s "123"; } private void upd
使用jsp直接执行定时任务
使用jsp直接执行定时任务servicehtml<%@ page import"com.leasing.emogo.framework.util.ApplicationContextUtils" %<%@ page import"job.dsc.GetInfoByAssetPackageJob" %<%@ page contentType
2021前端技术面试必备Vue:(一)基础快速学习篇
由于疫情的影响,相信很多小伙伴都在家里待着。中小公司由于运营困难会出现裁员, 我们也面临着 '失业',你是否感到了焦虑.最近做了个调研: '现在的你找到工作了吗 ?<br/1.大部分的回复: 求职平台都是 ‘已回复’,然后没有下文,你遇到了吗?<br/2.各个公司对技术的要求增高<br/3.有人说开始搞副业<br/ 在我来看,这一年已经过去了四分
几个你不知道的dubbo注册中心细节
你会正确配置backup地址吗?在配置dubbo注册中心时,一般会这样写dubbo.registry.protocolzookeeperdubbo.registry.address127.0.0.1:2181也会简单地写成dubbo.registry.addresszookeeper://127.0.0.1:2181当z
你的镜像安全吗?
你的镜像安全吗?与传统的服务器和虚拟机相比,Docker容器为我们工作提供了更安全的环境。容器中可以使我们的应用环境组件实现更小,更轻。每个应用的组件彼此隔离并且大大减少了攻击面。这样即使有人入侵了您的应用,也会最大程度限制被攻击的程度,而且入侵后,利用漏洞传播攻击更难。不过,我们还是需要最大程度了解Docker技术本身的存在的安全隐患,这样
程序员怎样写出搞垮公司的代码?
1、乱写注释 注释就像内裤,外面看不见,但是很重要。 注释要严谨,不能有明显的漏洞。如果你的内裤有漏洞,你不尴尬吗?当然了,如果你实力够强大,别人会尴尬。 2、代码和显示不一致 界面上是Post code,代码里是Zip code。看代码看到怀疑人生! 所以说年轻人,你只看到了第二层,你以为我在第一层,实际上我在第五层,你明白我在讲什么吗?
Java里面的十万个为什么
Java里面的十万个为什么 1.不是说 JVM 是运行 Java 程序的虚拟机吗?那 JRE 和 JVM 的关系是怎么样的呢?简单地说,JRE 包含 JVM 。JVM 是运行 Java 程序的核心虚拟机,而运行 Java 程序不仅需要核心虚拟机,还需要其他的类加载器,字节码校验器以及大量的基础类库。JRE 除包含 JVM 之外,还包含运行 Java 程序的其
您知道JavaScript中的0.1 + 0.2 ≠ 0.3吗?
嘿👋自从我使用JavaScript已有一段时间了。昨天,我经历了一个非常奇怪的行为。同时我真的很困惑和惊讶😕。最初我以为,我发现了一个论点再次诅咒JavaScript。但是,经过一些研究,我发现这不是错误。这是数学,也是计算机处理数字的方式。好吧,还有其他一些怪异的东西 幕后发生了什么?它背后的简单逻辑是计算机使用以2为基的(二进制)浮点数系统。让我们用一个
你写的Python代码规范吗?
总第141篇/张俊红1.什么是PEP8PEP 是 Python Enhancement Proposals 的缩写,直译过来就是「Python增强建议书」也可叫做「Python改进建议书」,说的直白点就是Python相关的一些文档,主要用来传递某些信息,这些信息包括某个通知亦或是某个新的规范。关于更深层次的概念,大家有兴趣的可以自行去了解。PEP 后面的数字
推荐程序员面试秘籍!2021年大厂Java岗面试必问
01 JAVA基础 1.1 java知识点 Hashmap 源码级掌握,扩容,红黑树,最小树化容量,hash冲突解决,有些面试官会提出发自灵魂的审问,比如为什么是红黑树,别的树不可以吗;为什么8的时候树化,4不可以吗,等等 concureentHashMap,段锁,如何分段,和hashmap在hash上的区别,性能,等等 HashTable ,同步锁,这块可
阿里程序员的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是一