处理 TreeSet 中的重复项

Question

我正在解决一个问题，我们必须找到每个 window（滑动 window）的中位数。我知道 treeset 不允许重复。所以我写了一个自定义比较器来使用元素索引而不是值。

代码如下：-

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

在两个比较器中，我 return 1 当两个值相同时打破关系，否则，如果我 return 0，treeset 将认为它们相同。如果我表现得很奇怪使用该语句。但是，如果我在两个值相等时将 "return 1" 替换为 "return y-x"，则效果很好。

谁能帮我理解这种行为？

谢谢。

Answer 1

您的 return 1; 语句违反了 Comparator 的 compare 方法的约定，因为这意味着如果 a[x]==a[y]，compare(x,y) 将 return 1 和 compare(y,x) 也将 return 1，并打破 sgn(compare(x, y)) ==-sgn(compare(y, x)) 要求。

处理 TreeSet 中的重复项

Handling duplicates in TreeSet

java

heap

treeset

data-structures