Java比对二维Comparable数组集合时如何正确计算含重复值的公共元素

原代码核心缺陷 #

• 使用==比较Comparable类型对象，本质是引用地址判等而非值比较，对非基础包装类的元素会直接产生逻辑错误；即使对Integer、Long这类缓存范围的包装类型，超出缓存区间的比较结果也会失效
• 引入commonList.contains()判断是否允许添加元素的逻辑，完全偏离了「按频次统计公共重复元素」的需求：公共重复元素的合法出现次数，等于该元素在所有输入数组中出现次数的最小值，而非只要出现过一次就禁止后续添加
• 每轮数组比对时没有新建临时列表存储当前轮次的交集结果，直接复用跨轮次的公共列表做累加，导致多轮比对时元素被重复计数，出现三个数组都仅含单个4却返回两个4的错误结果

正确实现路径 #

• 对每个输入数组预先排序，为双指针求多集交集做准备
• 每轮比对时，将上一轮得到的公共元素序列，与下一个输入数组求多集交集：通过双指针同步遍历两个已排序序列，按元素值大小移动指针，元素相等时就记录到临时交集列表，指针同步后移，完全按实际最小频次计数，不做去重处理
• 全部数组比对完成后，最终的交集列表就是所有数组的公共元素集合，天然支持重复值的准确统计

修正后代码实现 #

import java.util.Arrays;
import java.util.ArrayList;

public class CommonElements {
    private int comparisons = 0;

    public Comparable<?>[] findCommonElements(Comparable<?>[][] collections) {
        // 空集合兜底
        if (collections == null || collections.length == 0) {
            return new Comparable[0];
        }
        // 单数组场景直接返回
        if (collections.length == 1) {
            return collections[0];
        }

        // 初始公共序列为第一个数组，预先排序
        Comparable<?>[] currentCommon = collections[0];
        Arrays.sort(currentCommon);

        // 逐个数组求多集交集
        for (int i = 1; i < collections.length; i++) {
            Comparable<?>[] nextArr = collections[i];
            Arrays.sort(nextArr);
            ArrayList<Comparable<?>> tempIntersection = new ArrayList<>();
            
            int p1 = 0, p2 = 0;
            // 双指针遍历两个已排序序列求交集
            while (p1 < currentCommon.length && p2 < nextArr.length) {
                Comparable<?> e1 = currentCommon[p1];
                Comparable<?> e2 = nextArr[p2];
                comparisons++;
                
                @SuppressWarnings("unchecked")
                int cmp = ((Comparable<Object>) e1).compareTo(e2);
                if (cmp == 0) {
                    // 元素相等则记录，双指针同步后移，按频次计数
                    tempIntersection.add(e1);
                    p1++;
                    p2++;
                } else if (cmp < 0) {
                    // 当前公共序列元素更小，移动指针1
                    p1++;
                } else {
                    // 待比对数组元素更小，移动指针2
                    p2++;
                }
            }
            
            // 交集为空则无公共元素，提前返回
            if (tempIntersection.isEmpty()) {
                return new Comparable[0];
            }
            // 更新下一轮比对的公共序列为当前交集结果
            currentCommon = tempIntersection.toArray(new Comparable[0]);
        }
        return currentCommon;
    }

    public int getComparisons() {
        return comparisons;
    }
}

验证效果 #

• 输入集合{{1,1,1,1}, {1,1,1,3}, {1,1,1,5}}，第一轮交集从两个数组中统计得到3个公共1，第二轮与第三个数组比对仍保留3个1，最终输出{1,1,1}，符合重复元素统计要求
• 输入集合{{4,7,9}, {4,5,6}, {1,3,4}}，第一轮交集从两个数组中统计得到1个公共4，第二轮与第三个数组比对仍保留1个4，最终输出{4}，不会出现重复计数错误

内容的提问来源于stack exchange，提问作者Ochretis