获得不正确的排序顺序

Question

失败的测试用例：

输入： [-2147483648,1,1]
输出： -2147483648
预计： 1

当-2147483648 是这里的第二大数字时，为什么输出预期为 1？

public int thirdMax(int[] nums) {

    PriorityQueue<Integer> pq = new PriorityQueue(new Comparator<Integer>(){
        public int compare(Integer a, Integer b){return b-a;}
    });

    int res=0;

    for(int num : nums){
        if(!pq.contains(num)  )
            pq.add(num);

    }

    if(pq.size()<=2){
       for(int i=0; i<pq.size(); i++){
            res=pq.poll();
        }             
    }
    else {
        for(int i=0; i<3; i++){
            res=pq.poll();
        }        
    }
    return res;   
}

Answer 1

您的比较方法不适合 int。

而不是：

return b - a;

你应该做的：

return Integer.compare(b, a);

一个 int 最多只能保存 Integer.MAX_VALUE 个值。但是，如果您执行 1 - -2147483648，结果会大于 Integer.MAX_VALUE，这又会导致它再次为负 - 结果您会得到错误的排序顺序。基本上，return b - a; 只有在您知道所有数字都是正数（或者数字不会比 Integer.MAX_VALUE 更远）的情况下才是安全的。

其他情况可以使用API方法Integer.compare。

请注意，由于您是按整数自然顺序的倒数进行比较，您还可以缩短代码：

PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());

获得不正确的排序顺序

Getting incorrect sort order

java

priority-queue