java - 处理 TreeSet 中的重复项

Question

我正在解决一个问题，我们必须找到每个窗口(滑动窗口)的中位数。我知道树集不允许重复。因此，我编写了一个自定义比较器来使用元素索引而不是值。

下面是代码:-

class Solution {

     static int a[];
     static TreeSet<Integer> minheap;
     static TreeSet<Integer> maxheap;

     static class comp implements Comparator<Integer>
     {
         public int compare(Integer x,Integer y)
         {
             if(a[x]<a[y]) return -1;
             if(a[x]>a[y]) return 1;
             return 1;
         }
     }

    static class comp1 implements Comparator<Integer>
     {
         public int compare(Integer x,Integer y)
         {
             if(a[x]>a[y]) return -1;
             if(a[x]<a[y]) return 1;
             return 1;
         }
     }

     public void balance()
     {
         if(maxheap.size()>minheap.size()+1)
         {
             int temp=maxheap.pollFirst();
             minheap.add(temp);
         }
     }

     public void addNum(int num) {
        maxheap.add(num);
        balance();
        if(!maxheap.isEmpty() && !minheap.isEmpty() && a[maxheap.first()]>a[minheap.first()])
        {
            int temp1=minheap.pollFirst();
            int temp2=maxheap.pollFirst();

            minheap.add(temp2);
            maxheap.add(temp1);
        }
    }

    public double findMedian() {
        int size=maxheap.size()+minheap.size();
        if(size%2==1) return a[maxheap.first()];
        else return ((double)a[maxheap.first()] + a[minheap.first()])/2;
    }

    public double[] medianSlidingWindow(int[] nums, int k) {
        minheap=new TreeSet<Integer>(new comp());
        maxheap=new TreeSet<Integer>(new comp1());

        a=new int[nums.length];
        for(int i=0;i<nums.length;i++)
            a[i]=nums[i];

        double ans[]=new double[nums.length-k+1];

        int j=0;

        for(int i=0;i<k;i++)
            addNum(i);

        for(int i=k;i<nums.length;i++)
        {
            ans[j++]=findMedian();
            if(minheap.contains(i-k))
                minheap.remove(i-k);    
            else
                maxheap.remove(i-k);
            balance();
            addNum(i);
        }

        ans[j++]=findMedian();
        return ans;
    }
}

在两个比较器中，当两个值相同时我返回 1 以打破联系，否则，如果我返回 0，treeset 会将它们视为相同。如果我使用该语句，则行为会很奇怪。但是，如果我在两个值相等时将“return 1”替换为“return y-x”，则效果很好。

有人可以帮助我理解这种行为吗？

谢谢。

Answer 1

您的 return 1; 语句破坏了 Comparator 的 compare 方法的约定，因为它意味着 if a[ x]==a[y]，compare(x,y) 将返回 1 和 compare(y,x)还将返回 1，并违反 sgn(compare(x, y)) ==-sgn(compare(y, x)) 要求。