List Merge的小算法

今天说一个算法小甜点，因为对于算法知之甚少，所以完全是自己揣摩出来的一则，写出来只是个记录，如有更学术派的解法欢迎评论。

场景

我们系统有一个去重的需求，但是查重的维度是多方面的，举个例子，若干个用户用了用一个手机号，那么我们就认为他们是同一个人，用手机号码这个条件可以查出一组这样的人。同理用Email也是。

但是存在一个问题就是用手机号查出了5组人，用Email查出了3组人，最后我们可以认为重复的人是8吗？其实是不行的，因为有可能某几个人的手机号和Email都是一样的，那么在两次查询后都会将这些人纳入到统计中。所以最后统计出的结果应该是<=各次查询结果之和的。

解决方案

首先是数据结构，每次查询出来的结构是一个List，那么List里面其实又是一组重复的人。

为了方便理解，我们可以定义一个最小化结构为Group，

public class Group {

    private List<Long> duplications = new ArrayList<>();

}

里面的duplicates代表原始记录ID列表，举例说就是ID=13和ID=15的两条记录都是用的同一个手机号，那么duplications就是{13,15}。

每通过一个条件查询可以得到一个List的返回，很好理解，这个List的size就是说明有多少人用了相同的手机号。那么用Email查询的话结果就是代表多少人用了相同的Email。

假设ID=13的这条记录，它已经在用手机号查询的结果中被GroupA收录，如果它又在Email查询的结果中被GroupF收录的话，说明了什么问题？说明其实GroupA和GroupF应该取个合集，他们都是代表了同一个人。有点类似消消乐的意思。我们最后其实不管是通过什么条件查出来的，只要是一个Group的集合就好了。

// 先定义一个篮子
List<Group> duplicateBucket = new ArrayList<>();
for (// 若干条件) {
    List<Group> duplicates = queryProvider.queryDuplications();
    duplicateBucket.addAll(duplicates);
}
// 对这个篮子做一次去重
DeduplicationUtils.intersection(duplicateBucket);

再看这个去重的逻辑

public static void intersection(List<Grouop> duplicates) {
    for (int i = duplicates.size() - 2; i >= 0; i--) {
        for (int j = duplicates.size() - 1; j > i; j--) {
            Set<Long> setA = duplicates.get(i).toSet();
            Set<Long> setB = duplicates.get(j).toSet();
            Set intersection = Sets.intersection(setA, setB);
            if (intersection.size() > 0) {
                // 找出差集做合并
                List<Long> differences = new ArrayList<>();
                for (Long id : duplicates.get(j).getDuplications()) {
                    if (intersection.contains(id)) {
                        continue;
                    }
                    differences.add(id);
                }
                duplicates.get(i).addAllDuplications(differences);
                duplicates.remove(j);
            }
        }
    }
}

这里是关键，实际上就是双层遍历做对比，发现重复条目就做消消乐，让后者融合进前者的集合中去。

小结

这样就基本解决了去重的问题，但是效率一般，毕竟有双重循环在。如有更好的办法欢迎留言。