为了账号安全,请及时绑定邮箱和手机立即绑定

处理 TreeSet 中的重复项

处理 TreeSet 中的重复项

皈依舞 2023-08-23 17:08:04
我正在解决一个问题,我们必须找到每个窗口(滑动窗口)的中位数。我知道树集不允许重复。因此,我编写了一个自定义比较器来使用元素索引而不是值。下面是代码:-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);在两个比较器中,当两个值相同时我返回 1 以打破联系,否则,如果我返回 0,treeset 会将它们视为相同。如果我使用该语句,则行为会很奇怪。但是,如果我在两个值相等时将“return 1”替换为“return yx”,则效果很好。有人可以帮助我理解这种行为吗?
查看完整描述

1 回答

?
HUH函数

TA贡献1836条经验 获得超4个赞

您的语句破坏了's方法return 1;的约定,因为这意味着 if , will return并且也将 return ,并且违反了要求。Comparatorcomparea[x]==a[y]compare(x,y)1compare(y,x)1sgn(compare(x, y)) ==-sgn(compare(y, x))



查看完整回答
反对 回复 2023-08-23
  • 1 回答
  • 0 关注
  • 108 浏览

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信