題目

這是lintcode上的一道題，上次看別人發(fā)了后自己試著寫了一下虱歪。感覺是比較沒有技術(shù)含量的解題思路吧，而且上次面試時候也有遇到過栅表，就當(dāng)做個記錄笋鄙。

以下是題目：
·····································
給定一個包含 n 個整數(shù)的數(shù)組，和一個大小為 k 的滑動窗口,從左到右在數(shù)組中滑動這個窗口怪瓶，找到數(shù)組中每個窗口內(nèi)的中位數(shù)萧落。(如果數(shù)組個數(shù)是偶數(shù)，則在該窗口排序數(shù)字后，返回第 N/2 個數(shù)字找岖。)

樣例
對于數(shù)組 [1,2,7,8,5], 滑動大小 k = 3 的窗口時陨倡，返回 [2,7,7]
最初，窗口的數(shù)組是這樣的：
[ | 1,2,7 | ,8,5] , 返回中位數(shù) 2;
接著许布，窗口繼續(xù)向前滑動一次兴革。
[1, | 2,7,8 | ,5], 返回中位數(shù) 7;
接著，窗口繼續(xù)向前滑動一次蜜唾。
[1,2, | 7,8,5 | ], 返回中位數(shù) 7;

·····································

代碼

import java.util.Comparator;
import java.util.List;

public class Solution {


    public static void main(String[] args){
        System.out.println(medianSlidingWindow(new int[]{1,2,7,7,2},3));
    }

    /**
     * @param nums: A list of integers
     * @param k: An integer
     * @return: The median of the element inside the window at each moving
     */
    public static List<Integer> medianSlidingWindow(int[] nums, int k) {
        // write your code here
        if (nums == null || nums.length == 0 || k <= 0)return new ArrayList<Integer>();
        int left = 0;
        int right = k -1;
        List<Data> temp = new ArrayList<>();
        List<Integer> result = new ArrayList<>();
        for (int i = left;i<right;i++){
            temp.add(new Data(i,nums[i]));
        }
        temp.sort(new MyCom());
        int curLeft = 0;
        for (;right < nums.length;left++,right++){
            Data target = new Data(right,nums[right]);
            boolean insertTarget = false,findPos = false;
            for (int j = 0;j<temp.size();j++){
                Data data = temp.get(j);
                if (data.value >=target.value && !insertTarget){
                    temp.add(j,target);
                    j++;
                    insertTarget = true;
                }
                if (data.pos == left && !findPos){
                    curLeft = j;
                    findPos = true;
                }
                if (insertTarget && findPos)break;
            }
            if (!insertTarget)
                temp.add(target);
            result.add(temp.get((temp.size()-1) / 2).value);
            temp.remove(curLeft);
        }

        return result;
    }

    static class Data{
        public Data(int pos,int value){
            this.pos = pos;
            this.value = value;
        }
        int pos;
        int value;
    }

    static class MyCom implements Comparator<Data> {

        @Override
        public int compare(Data o1, Data o2) {
            if (o1.value > o2.value)return 1;
            if (o1.value == o2.value)return 0;
            return -1;
        }

        @Override
        public boolean equals(Object obj) {
            return false;
        }
    }
}