我正在解決一個問題,我們必須找到每個窗口(滑動窗口)的中位數(shù)。我知道樹集不允許重復(fù)。因此,我編寫了一個自定義比較器來使用元素索引而不是值。下面是代碼:-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);在兩個比較器中,當(dāng)兩個值相同時我返回 1 以打破聯(lián)系,否則,如果我返回 0,treeset 會將它們視為相同。如果我使用該語句,則行為會很奇怪。但是,如果我在兩個值相等時將“return 1”替換為“return yx”,則效果很好。有人可以幫助我理解這種行為嗎?
1 回答

HUH函數(shù)
TA貢獻(xiàn)1836條經(jīng)驗 獲得超4個贊
您的語句破壞了's方法return 1;
的約定,因為這意味著 if , will return并且也將 return ,并且違反了要求。Comparator
compare
a[x]==a[y]
compare(x,y)
1
compare(y,x)
1
sgn(compare(x, y)) ==-sgn(compare(y, x))
添加回答
舉報
0/150
提交
取消