为何Comparator.comparingInt与new Comparator效果不一致？

题目描述 #

超级丑数是指其所有质因数都在给定质数数组primes中的正整数。
给定整数n和质数数组primes，返回第n个超级丑数。
保证第n个超级丑数在32位有符号整数范围内。

问题场景 #

在测试用例 n = 5911、primes = [2,3,5,7] 时，两种Comparator写法得到完全不同的结果：

• 使用Comparator.comparingInt的代码返回 -2147483648（错误结果）
• 使用匿名内部类new Comparator的代码返回 2144153025（正确结果）

错误代码（Comparator.comparingInt版本） #

public int nthSuperUglyNumber(int n, int[] primes) {
    int[] rets = new int[n];
    PriorityQueue<PrimeCandidate> priorityQueue = new PriorityQueue<>(primes.length, Comparator.comparingInt(o -> o.num));
    for (int i = 0; i < primes.length; i++) priorityQueue.offer(new PrimeCandidate(primes[i], primes[i], 1));
    rets[0] = 1;

    for(int i = 1; i < n; i++) {
        rets[i] = priorityQueue.peek().num;
        while(priorityQueue.peek().num == rets[i]) {
            PrimeCandidate droppedPrimecandidate = priorityQueue.poll();
            priorityQueue.offer(new PrimeCandidate(rets[droppedPrimecandidate.index]*droppedPrimecandidate.prime
                    , droppedPrimecandidate.prime, droppedPrimecandidate.index+1));
        }
    }
    return rets[n-1];
}

class PrimeCandidate {
    int num;
    int prime;
    int index;
    PrimeCandidate(int num, int prime, int index) {
        this.num = num;
        this.prime = prime;
        this.index = index;
    }
}

正确代码（匿名Comparator版本） #

public int nthSuperUglyNumber(int n, int[] primes) {
    int[] rets = new int[n];
    PriorityQueue<PrimeCandidate> priorityQueue = new PriorityQueue<>(primes.length, new Comparator<PrimeCandidate>() {
        @Override
        public int compare(PrimeCandidate o1, PrimeCandidate o2) {
            return o1.num - o2.num;
        }
    });
    for (int i = 0; i < primes.length; i++) priorityQueue.offer(new PrimeCandidate(primes[i], primes[i], 1));
    rets[0] = 1;

    for(int i = 1; i < n; i++) {
        rets[i] = priorityQueue.peek().num;
        while(priorityQueue.peek().num == rets[i]) {
            PrimeCandidate droppedPrimecandidate = priorityQueue.poll();
            priorityQueue.offer(new PrimeCandidate(rets[droppedPrimecandidate.index]*droppedPrimecandidate.prime
                    , droppedPrimecandidate.prime, droppedPrimecandidate.index+1));
        }
    }
    return rets[n-1];
}

class PrimeCandidate {
    int num;
    int prime;
    int index;
    PrimeCandidate(int num, int prime, int index) {
        this.num = num;
        this.prime = prime;
        this.index = index;
    }
}

差异原因分析 #

两种写法的核心差异在于整数溢出场景下的比较逻辑不同：

1. 匿名Comparator的巧合正确性
   手动实现的return o1.num - o2.num存在严重的整数溢出风险：当o1.num为正数、o2.num为溢出产生的负数时，o1.num - o2.num会超出int取值范围，溢出后得到错误的负数结果，导致Comparator错误判定o1.num < o2.num。在你的测试场景中，这种错误逻辑恰好让溢出的负数没有被优先取出，队列始终处理合法的正整数丑数，最终得到正确结果，但这是偶然情况，写法本身不安全。

2. Comparator.comparingInt的严格正确性
   Comparator.comparingInt(o -> o.num)内部使用Integer.compare(o1.num, o2.num)实现比较，这是Java官方推荐的安全比较方式：它会直接根据int的数值大小（包括补码表示的负数）返回正确的比较结果。当代码生成溢出的负数num时，Integer.compare会正确识别负数是最小的int值，将其放在PriorityQueue头部，导致后续取出负数作为丑数，最终返回错误结果。

3. 根本问题
   两种写法的差异暴露了代码的核心隐患：计算rets[droppedPrimecandidate.index] * droppedPrimecandidate.prime时会发生整数溢出，生成不符合要求的负数。虽然题目保证第n个丑数在32位有符号整数范围内，但中间步骤的乘积可能超出范围，需要做溢出防护。

修复方案 #

修改PrimeCandidate的num字段为long类型，用long存储中间乘积避免溢出：

class PrimeCandidate {
    long num;
    int prime;
    int index;
    PrimeCandidate(long num, int prime, int index) {
        this.num = num;
        this.prime = prime;
        this.index = index;
    }
}

// 调整PriorityQueue的Comparator为comparingLong
PriorityQueue<PrimeCandidate> priorityQueue = new PriorityQueue<>(primes.length, Comparator.comparingLong(o -> o.num));

// 生成新候选时用long计算乘积
priorityQueue.offer(new PrimeCandidate((long)rets[droppedPrimecandidate.index] * droppedPrimecandidate.prime
        , droppedPrimecandidate.prime, droppedPrimecandidate.index+1));

内容的提问来源于stack exchange，提问作者ENTITY 2 is 1