如何从两个List中筛选出相同的值

问题

现有社保卡和身份证若干,想要匹配筛选出一一对应的社保卡和身份证。 转换为List<社保卡> socialList,和List idList,从二者中找出匹配的社保卡。

模型

创建社保卡类

/**
 * @author Ryan Miao
 */
class SocialSecurity{
    private Integer id;//社保号码
    private Integer idCard;//身份证号码
    private String somethingElse;

    public SocialSecurity(Integer id, Integer idCard, String somethingElse) {
        this.id = id;
        this.idCard = idCard;
        this.somethingElse = somethingElse;
    }

    public Integer getId() {
        return id;
    }

    public Integer getIdCard() {
        return idCard;
    }

    public String getSomethingElse() {
        return somethingElse;
    }

    @Override
    public String toString() {
        return "SocialSecurity{" +
                "id=" + id +
                ", idCard=" + idCard +
                ", somethingElse='" + somethingElse + '\'' +
                '}';
    }
}

创建身份证类

class IdCard {
    private Integer id;//身份证号码
    private String somethingElse;

    public IdCard(Integer id, String somethingElse) {
        this.id = id;
        this.somethingElse = somethingElse;
    }

    public Integer getId() {
        return id;
    }

    public String getSomethingElse() {
        return somethingElse;
    }

    @Override
    public String toString() {
        return "IdCard{" +
                "id=" + id +
                ", somethingElse='" + somethingElse + '\'' +
                '}';
    }
}

最简单的办法:遍历

只要做两轮循环即可。 准备初始化数据:

private ArrayList<SocialSecurity> socialSecurities;
private ArrayList<IdCard> idCards;

@Before
public void setUp(){
    socialSecurities = Lists.newArrayList(
            new SocialSecurity(1, 12, "小明"),
            new SocialSecurity(2, 13, "小红"),
            new SocialSecurity(3, 14, "小王"),
            new SocialSecurity(4, 15, "小peng")
    );

    idCards = Lists.newArrayList(
            new IdCard(14, "xiaopeng"),
    new IdCard(13, "xiaohong"),
    new IdCard(12, "xiaoming")
    );

    //目标: 从socialSecurities中筛选出idCards中存在的卡片
}

遍历

 @Test
public void testFilterForEach(){
    List<SocialSecurity> result = new ArrayList<>();
    int count = 0;
    for (SocialSecurity socialSecurity : socialSecurities) {
        for (IdCard idCard : idCards) {
            count++;
            if (socialSecurity.getIdCard().equals(idCard.getId())){
                result.add(socialSecurity);
            }
        }
    }

    System.out.println(result);
    System.out.println(count);//12 = 3 * 4
    //O(m,n) = m*n;
}

很容易看出,时间复杂度O(m,n)=m*n.

采用Hash

通过观察发现,两个list取相同的部分时,每次都遍历两个list。那么,可以把判断条件放入Hash中,判断hash是否存在来代替遍历查找。

@Test
public void testFilterHash(){
    Set<Integer> ids = idCards
            .stream()
            .map(IdCard::getId)
            .collect(Collectors.toSet());
    List<SocialSecurity> result = socialSecurities
            .stream()
            .filter(e->ids.contains(e.getIdCard()))
            .collect(Collectors.toList());

    System.out.println(result);
    //初始化 hash 3
    //遍历socialSecurities 4
    //从hash中判断key是否存在  4
    //O(m,n)=2m+n=11
}

如此,假设hash算法特别好,hash的时间复杂度为O(n)=n。如此推出这种做法的时间复杂度为O(m,n)=2m+n. 当然,更重要的是这种写法更让人喜欢,天然不喜欢嵌套的判断,喜欢扁平化的风格。

Hash一定会比遍历快吗

想当然的以为,hash肯定会比遍历快,因为是hash啊。其实,可以算算比较结果。比较什么时候2m+n < m*n。 从数据归纳法的角度,n必须大于2,不然即演变程2m+2 < 2m。于是,当n>2时:

@Test
public void testCondition(){
    int maxN = 0;
    for (int m = 2; m < 100; m++) {
        for (int n = 3; n < 100; n++) {
            if ((2*m+n)>m*n){
                System.out.println("m="+m +",n="+n);
                if (n>maxN){
                    maxN = n;
                }
            }
        }
    }

    System.out.println(maxN);
}

结果是:

m=2,n=3
3

也就是说n<=3的时候,遍历要比hash快。事实上还要更快,因为hash还需要创建更多的对象。然而,大部分情况下,n也就是第二个数组的长度是大于3的。这就是为什么说hash要更好写。当然,另一个很重要的原因是lambda stream的运算符号远比嵌套循环让人喜爱。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏程序猿DD

第四章 正则表达式回溯法原理

第四章 正则表达式回溯法原理 学习正则表达式,是需要懂点儿匹配原理的。 而研究匹配原理时,有两个字出现的频率比较高:“回溯”。 听起来挺高大上,确实还有很多人...

1886
来自专栏calmound

UVA 10003 Cutting Sticks(区间DP)

题意: 有一根长度为l的木棍,木棍上面有m个切割点,每一次切割都要付出当前木棍长度的代价,问怎样切割有最小代价 在完成这道题目之前,我们先熟悉一下区间DP 对于...

2808
来自专栏九彩拼盘的叨叨叨

requestAnimationFrame简介

当我们写window.requestAnimationFrame(回调函数)时,浏览器会在下次重绘前执行回调函数。

462

视觉搜索和Neo4j的最后一公里

“ 最后一公里 ”是电信行业使用的一个术语,指系统为实际使用该系统的客户提供链接。就图形数据库而言,它指的是终端用户可以从图中提取有价值的信息和洞察力。我们...

1563
来自专栏C语言及其他语言

[每日一题]定义和调用函数fact(k)计算k的阶乘

在C语言的学习过程中,其实最好的提升能力的方式就是刷题,能够在题海中正真锻炼自己的逻辑思维能力和动手能力,所以先来看看下面这题陶冶陶冶情操。 题目描述 编写程...

3934
来自专栏儿童编程

【Scratch编程与艺术-1】简单与重复的艺术

利用Scratch的“图章”功能,能够实现非常美的效果。我们可以称之为简单的艺术。我们需要做的就是把下面的代码加在某一对象身上。点击开始按钮,就可以静静地欣赏亲...

742
来自专栏九彩拼盘的叨叨叨

彭小六私密日更群日更活动目录生成代码

1234
来自专栏每日一篇技术文章

OpenGLES_实战04_教你绘制球体

写这篇文章主要给初学者一个绘制球体的思路,苹果给我们封装的类,帮助我们简化了不少代码,如果纯OpenGL 做这样一个练习代码量还是挺多的。

611
来自专栏专知

关关的刷题日记07——Leetcode 26. Remove Duplicates from Sorted Array 方法1

关小刷刷题07 – Leetcode 26. Remove Duplicates from Sorted Array 方法1 题目 Given a sorted...

2644
来自专栏hrscy

202 - Swift 的核心是什么?

不知道大家有没有看过 WWDC 2015 的视频,其中有一个编号为 408 的视频解释了这个问题,下面是视频链接:Protocol-Oriented Progr...

782

扫描关注云+社区