題意：給定一個數(shù)組和一個滑動窗口，返回每一個滑動窗口的中位數(shù)

思路：遍歷數(shù)組

1. 維護(hù)一個最小的treeset，和一個最大的treeset，記錄當(dāng)前節(jié)點(diǎn)的index
2. 每次根據(jù)奇偶返回當(dāng)前的中位數(shù)

思想：treeset

復(fù)雜度：時間O（nlgk)，空間O(k)

class Solution {
    public double[] medianSlidingWindow(int[] nums, int k) {
        TreeSet<Integer> set1 = new TreeSet(new Comparator<Integer>(){
           public int compare(Integer n1, Integer n2) {
               if(nums[n2] == nums[n1])
                   return n1 - n2;
               return Integer.compare(nums[n1], nums[n2]);
           } 
        });
        TreeSet<Integer> set2 = new TreeSet(new Comparator<Integer>(){
           public int compare(Integer n1, Integer n2) {
               if(nums[n2] == nums[n1])
                   return n1 - n2;
               return Integer.compare(nums[n2], nums[n1]);
           } 
        });
        
        double[] res = new double[nums.length - k + 1];
        
        for(int i=0;i<nums.length;i++) {
            if(i>=k) {
                res[i - k] = get(set1, set2, nums);
                remove(i-k, set1, set2, nums);
            }
            add(i, set1, set2, nums);
        }
        res[nums.length - k] = get(set1, set2, nums);
        return res;
    }
    
    void add(int n1, TreeSet<Integer> set1, TreeSet<Integer> set2, int[] nums) {
        if(set1.isEmpty() || nums[n1] >= nums[set1.first()]) {
            set1.add(n1);
        } else {
            set2.add(n1);
        }
        if(set1.size() < set2.size())
            set1.add(set2.pollFirst());
        
        if(set1.size() - set2.size() > 1)
            set2.add(set1.pollFirst());
    }
        
    void remove(int n1, TreeSet<Integer> set1, TreeSet<Integer> set2, int[] nums) {
        if(set1.contains(n1)) {
            set1.remove(n1);
        } else {
            set2.remove(n1);
        }
        if(set1.size() < set2.size())
            set1.add(set2.pollFirst());
        
        if(set1.size() - set2.size() > 1)
            set2.add(set1.pollFirst());
    }
    
    double get(TreeSet<Integer> set1, TreeSet<Integer> set2, int[] nums) {
        if(set1.size() == set2.size()) {
            return ((double)nums[set1.first()] + (double)nums[set2.first()]) / 2;
        } else {
            return (double)nums[set1.first()];
        }
    }
}