如何从两个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 条评论
登录 后参与评论

相关文章

来自专栏码匠的流水账

聊聊flink的BoltWrapper

flink-storm_2.11-1.6.2-sources.jar!/org/apache/flink/storm/wrappers/BoltWrapper....

1004
来自专栏码匠的流水账

聊聊storm WindowTridentProcessor的FreshCollector

本文主要研究一下storm WindowTridentProcessor的FreshCollector

813
来自专栏软件开发 -- 分享 互助 成长

C++ STL之排序算法

排序算法和查找算法差不多,也涉及到迭代器区间问题,关于该问题的注意事项就不在啰嗦了 一、全部排序sort、stable_sort sort是一种不稳定排序,使用...

1975
来自专栏闵开慧

曾经做过的40道程序设计课后习题总结(三)

曾经做过的40道程序设计课后习题总结(三) 课后习题目录 1 斐波那契数列 2 判断素数 3 水仙花数 4 分解质因数 5 杨辉三角 6 学习成绩查询 7 求最...

3968
来自专栏wym

2013年多校赛 hdu4607

   那么就考虑树上最长距离,树的直径, 如果访问的点大于树的直径就要走回头路,答案即多的数乘2加上原来树的直径

1205
来自专栏Java帮帮-微信公众号-技术文章全总结

【编程题】Java编程题一(10道)

【编程题】Java编程题一(10道) 【程序1】 题目:古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,...

4288
来自专栏数据结构与算法

2728 整数帝国问题

2728 整数帝国问题 时间限制: 1 s 空间限制: 16000 KB 题目等级 : 白银 Silver 题目描述 Description   ...

2996
来自专栏java达人

数字的陷阱

Java中对数字的处理,如四舍五入,如加减乘除,貌似是一个很基础很简单的知识点,但是如果你没有对他进行充分了解,很容易掉进它的陷阱里。 1、浮点数运算 先来看一...

1888
来自专栏HansBug's Lab

2431: [HAOI2009]逆序对数列

2431: [HAOI2009]逆序对数列 Time Limit: 5 Sec  Memory Limit: 128 MB Submit: 954  Solv...

2856
来自专栏草根专栏

用C#(.NET Core) 实现简单工厂和工厂方法设计模式

本文源自深入浅出设计模式. 只不过我是使用C#/.NET Core实现的例子. 前言 当你看见new这个关键字的时候, 就应该想到它是具体的实现. ? 这就是一...

6524

扫码关注云+社区