资讯专栏INFORMATION COLUMN

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

BothEyes1993 / 3606人阅读

摘要:转换为社保卡和,从二者中找出匹配的社保卡。准备初始化数据小明小红小王小目标从中筛选出中存在的卡片遍历很容易看出,时间复杂度采用通过观察发现,两个取相同的部分时,每次都遍历两个。

问题

现有社保卡和身份证若干,想要匹配筛选出一一对应的社保卡和身份证。
转换为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 socialSecurities;
private ArrayList 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 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 ids = idCards
            .stream()
            .map(IdCard::getId)
            .collect(Collectors.toSet());
    List 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的运算符号远比嵌套循环让人喜爱。

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/67645.html

相关文章

  • 零开始构造决策树(python)

    摘要:起步本章介绍如何不利用第三方库,仅用自带的标准库来构造一个决策树。构造决策树决策树中需要一个属性来指向树的根节点,以及特征数量。 起步 本章介绍如何不利用第三方库,仅用python自带的标准库来构造一个决策树。不过这可能需要你之前阅读过这方面的知识。 前置阅读 分类算法之决策树(理论篇) 分类算法之决策树(应用篇) 本文使用将使用《应用篇》中的训练集,向量特征仅有 0 和 1 两种情况...

    zhoutao 评论0 收藏0
  • 如何管理 vue 项目中的数据?

    摘要:如何管理项目的数据这个问题似乎早已经有答案了,无非就是使用,全局,整个应用维护一个超大的,界面的显示情况随着超大的变化而变化。 vuex 如何管理 vue 项目的数据?这个问题似乎早已经有答案了,无非就是使用 vuex ,全局 store,整个应用维护一个超大的 Object,界面的显示情况随着超大 Object 的变化而变化。 看起来很简单,不就维护一个 Object 嘛,实际上,要...

    starsfun 评论0 收藏0
  • Python编程规范笔记(上)

    摘要:编程规范笔记上写在前面从语言开始,自己陆续学习了,但是自从研究生做毕设接触以来,就爱不释手,再也没有动力尝试其他语言。一与的一大优势就是具备优秀的可读性,而这基于一套较为完整的公认编程规范。如原本希望的结果是,结果却完全一样。 Python编程规范笔记(上) 写在前面: 从C语言开始,自己陆续学习了C++/Java,但是自从研究生做毕设接触Python以来,就爱不释手,再也没有动力尝试...

    Kross 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<