题解 | #滑动窗口中位数#

思路: 自己维护一个窗口，使窗口里面的数字是有序的。如果能够做到这一点，那么我们每次取中位数就相当方便了。大致思路有了之后，我们应该解决下面问题

1. 窗口应该使用什么数据结构? 在这里，我们使用 ArrayList，选取的理由主要是查找速度相对于 LinkedList 更快。我们需要频繁地插入数据，每次数据插入的位置，我们都要进行 检索，使其插入合适的位置，才能保证窗口内的数据一直保持有序。
2. 每获取到一个数据后，如何在窗口内找到插入的位置? 这里我们使用 二分查找(O(logN))。在查找过程中，如果某个位置上的值 大于等于 当前值，直接在该位置上插入；如果小于，往后一位再插入。
3. 由于我们使用 ArrayList，因此，每一次插入的时间复杂度，都是 O(n)。 我们每一次插入，当前位置往后的数据都要进行移动，所以时间复杂度为 O(n)。

这里有几点需要主要:

1. 防止数据溢出。 (虽然在当前题目中，原始数组中的每个值都不会取到最大。) 因此在求，中位数为两个数的平均值时，要特别注意。
2. 精度的把握。 题目要求的返回值是 double 类型，需要注意。

最后，当前代码的用力通过率是 80%，有两个没有通过，超时了! 代码应该还能优化。这个代码我放在 Leetcode 上是能通过的，而且时间战胜了 30%多 的代码，在 牛客 上不知道为什么超时了，哎。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型ArrayList 
     * @param k int整型 
     * @return double浮点型ArrayList
     */
    public ArrayList<Double> slidewindow (ArrayList<Integer> nums, int k) {
        // write code here
        if (null == nums || nums.size() < 1 || nums.size() < k || k == 0) {
            return new ArrayList<Double>();
        }
        ArrayList<Double> ans = new ArrayList<>();
        if (k == 1) {
            for (int num : nums) {
                ans.add((double) num);
            }
            return ans;
        }
        ArrayList<Integer> sw = new ArrayList<>();
        for (int i = 0; i < nums.size(); i++) {
            if (sw.size() == 0) {
                sw.add(nums.get(i));
                continue;
            }
            int insertIndex = binarySearch(sw, nums.get(i));
            sw.add(insertIndex, nums.get(i));
            if (sw.size() > k) {
                sw.remove(Integer.valueOf(nums.get(i - k)));
            }
            if (sw.size() == k) {
                if (k % 2 == 0) {
                    int p1 = sw.size() / 2 - 1;
                    int p2 = sw.size() / 2;
                    int val1 = sw.get(p1);
                    int val2 = sw.get(p2);
                    ans.add(val1 + ((double) val2 - val1) / 2);
                } else {
                    int p = sw.size() / 2;
                    ans.add((double) sw.get(p));
                }
            }
        }
        return ans;
    }
    public static int binarySearch(ArrayList<Integer> sw, int target) {
        int l = 0;
        int r = sw.size() - 1;
        while (l < r) {
            int mid = l + ((r - l) >> 1);
            if (sw.get(mid) < target) {
                l = mid + 1;
            } else if (sw.get(mid) > target) {
                r = mid - 1;
            } else {
                return mid;
            }
        }
        return sw.get(l) > target ? l : l + 1;
    }
}