题目

这是lintcode上的一道题，上次看别人发了后自己试着写了一下。感觉是比较没有技术含量的解题思路吧，而且上次面试时候也有遇到过，就当做个记录。

以下是题目：
·····································
给定一个包含 n 个整数的数组，和一个大小为 k 的滑动窗口,从左到右在数组中滑动这个窗口，找到数组中每个窗口内的中位数。(如果数组个数是偶数，则在该窗口排序数字后，返回第 N/2 个数字。)

样例
对于数组 [1,2,7,8,5], 滑动大小 k = 3 的窗口时，返回 [2,7,7]
最初，窗口的数组是这样的：
[ | 1,2,7 | ,8,5] , 返回中位数 2;
接着，窗口继续向前滑动一次。
[1, | 2,7,8 | ,5], 返回中位数 7;
接着，窗口继续向前滑动一次。
[1,2, | 7,8,5 | ], 返回中位数 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;
        }
    }
}