java 为什么'Comparator.comparingInt'和'new Comparator'不一样?

qco9c6ql  于 2023-04-19  发布在  Java
关注(0)|答案(1)|浏览(254)

我一直在做leetcode上的一道算法题,题目是313,超级丑数,题目描述是
一个超级丑的数字是一个正整数,其素数因子是数组素数。
给定一个整数n和一个整数素数数组,返回第n个超级丑陋的数字。
第n个超级丑陋的数字保证适合32位有符号整数。
我的提交失败了一个案例。案例是n = 5911和primes = [2,3,5,7]。下面是我的代码,你可以看到我使用Comparator.comparingInt而不是IDEA建议的new Comparator。结果是-2147483648。

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;
        }
    }

然而,在我改回new Comparator后,结果是正确的,即2144153025。

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;
        }
    }

这背后的原因是什么?我认为这两种方法是等价的。

  • Idea建议使用'Comparator.comparingInt'来替换'new Comparator'。
  • 我在谷歌上搜索了Comparator.comparingInt的用法和源代码。所有这些都暗示这两者的工作方式相同。但在我的情况下并非如此。
zu0ti5jz

zu0ti5jz1#

Comparator.comparingInt是正确的,a - b是错误的。
问题是整数溢出。
想象一下,比较-5和2。显然,这应该返回一个负数(-5在2之前)。任何一个都会这样做。a - b返回一个负数,Comparator.comparingInt(a -> -5 or 2)所做的比较器也会返回一个负数。
但是现在想象一下比较-2^31-1和20。出于同样的原因,这也应该返回一个负数。但是,a - b返回一个正数由于溢出。
这就是为什么你不应该永远使用a - b作为比较器函数的实现的原因之一(以及为什么你应该听从linter工具的建议,使用comparingInt和正确的朋友-如果你手工完成,你将不得不编写if (a < b) return -1;等)。
奇怪的是,这意味着您期望Comparator.comparingInt给予正确答案,而a - b失败。
有可能leetcode的检查器是用相同的bug编写的(比如,他们的impl也有bug,因此实际上标记为正确的代码,其中有相同的bug,并标记为“不正确”的正确impl)。
假设你知道失败的测试用例,那么你可以同时运行两个测试用例,然后手动检查哪一个有正确的答案(如果需要的话,你可以使用wolfram alpha将一个数字拆分成素数),然后你就知道或者至少你可以检查这两个测试用例在已知的有问题的输入中有什么不同。

相关问题