如何从两个List中筛选出相同的值
2024-08-26 20:27:24
问题
现有社保卡和身份证若干，想要匹配筛选出一一对应的社保卡和身份证。
转换为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的运算符号远比嵌套循环让人喜爱。
最新文章
- [注意]SerialPort操作PCI-1621D多串口卡，出现异常"参数不正确"
- 动态规划VS分治策略
- Cocos2d-x-3.0 Touch事件处理机制
- 【CronExpression表达式详解和案例】
- ArcGIS中的WKID
- 在VS下使用 GitFlow管理项目开发
- Python socket编程之五：更新分时图
- poj 3259 Wormholes spfa算法
- c++ assert
- 编译时和运行时、OC中对象的动态编译机制
- HDOJ-ACM1020(JAVA)
- [CodeForce]358D Dima and Hares
- Understanding JavaScript Function Invocation and "this"
- JS、html打开超链接的几种形式
- Robot Framework学习笔记（八）------ride标签使用
- git push origin与git push -u origin master的区别
- 在qt creator中使用imread并将图片显示到QLable中时没反应
- 云笔记项目-Spring事务学习-传播Requried
- 力扣（LeetCode） 263. 丑数
- pycharm如何设置注释的字体颜色