如何从两个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 = wArrayList(
new SocialSecurity(1, 12, "⼩明"),
new SocialSecurity(2, 13, "⼩红"),
new SocialSecurity(3, 14, "⼩王"),
new SocialSecurity(4, 15, "⼩peng")
);
idCards = wArrayList(
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 (IdCard().Id())){
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)
.Set());
List<SocialSecurity> result = socialSecurities
.stream()
.filter(e-&IdCard()))
.List());
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的运算符号远⽐嵌套循环让⼈喜爱。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。