Обработка дубликатов в TreeSet - PullRequest
Новая
       23

Обработка дубликатов в TreeSet

0 голосов
/ 24 сентября 2019

Я решал вопрос, где мы должны найти медиану каждого окна (скользящее окно).Я знаю, что 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;
    }
}

В обоих компараторах я возвращаю 1, когда оба значения одинаковычтобы разорвать связи, как в противном случае, treeset будет считать их одинаковыми, если я верну 0. Это ведет себя странно, если я использую это утверждение.Однако, если я заменю «return 1» на «return yx», когда оба значения равны, это прекрасно работает.

Может кто-нибудь помочь мне понять это поведение?

Спасибо.

1 Ответ

3 голосов
/ 24 сентября 2019

Ваш оператор return 1; нарушает контракт метода Comparator compare, поскольку это означает, что если a[x]==a[y], compare(x,y) вернет 1 и compare(y,x) также вернет 1и нарушите требование sgn(compare(x, y)) ==-sgn(compare(y, x)).

...