问题:
滑动窗口中位数中位数是有序序列最两头的那个数。如果序列的大小是偶数，则没有最两头的数；此时中位数是最两头的两个数的平均数。例如：[2,3,4]，中位数是 3[2,3]，中位数是 (2 + 3) / 2 = 2.5给你一个数组 nums，有一个大小为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数，每次窗口向右挪动 1 位。你的工作是找出每次窗口挪动后失去的新窗口中元素的中位数，并输入由它们组成的数组。这个问题第一次解答的时候没有了解, 只给出了求中位数的解.
实际上还要简单一些, 而且这个问题的外围就在我没有了解的那一部分.
画一个图更容易了解这道题的意思:
给出 nums = [1,3,-1,-3,5,3,6,7\]，以及 k = 3。中括号内即为窗口数组[1 3 -1] -3 5 3 6 7 1 1 [3 -1 -3] 5 3 6 7 -1 1 3 [-1 -3 5] 3 6 7 -1 1 3 -1 [-3 5 3] 6 7 3 1 3 -1 -3 [5 3 6] 7 5 1 3 -1 -3 5 [3 6 7] 6我目前的解题思路很简略, 很暴力:
1, 遍历nums的所有窗口数组
2, 对每一个窗口数组排序, 取中位值
3, 获得所有中位值, 并打印
代码:
public class 滑动窗口中位数 { static List<int[]> tempList = new ArrayList<>(); static List<Double> midNumList = new ArrayList<>(); static int[] nums = new int[]{3,4,6,8,2,7}; static int k = 2; private static void getArrays(int[] nums, int k){ int left = 0; int right = k-1; getArraysUtil(nums, left, right, k); } private static void getArraysUtil(int[] nums, int left, int right, int k){ int temp[] = new int[k]; for (int i = 0; i < k; i++) { temp[i] = nums[left+i]; } tempList.add(temp); left++; right++; if (right<=(nums.length-1)) { getArraysUtil(nums, left, right, k); } } private static double getMidFromArray(int args[]){ double midNum = 0.0; List<Integer> intList = new ArrayList<Integer>(); for (int i = 0; i < args.length; i++) { intList.add(args[i]); } Collections.sort(intList); for (int i = 0; i < intList.size(); i++) { } int arraySize = intList.size(); if (arraySize%2 == 1) { midNum = intList.get((arraySize-1)/2); }else { midNum = (intList.get(arraySize/2 - 1) + intList.get(arraySize/2) + 0.0) / 2 ; } return midNum; } public static void main(String[] args) { // get all arrays getArrays(nums, k); // get Mid nums for (int i = 0; i < tempList.size(); i++) { midNumList.add(getMidFromArray(tempList.get(i))); } // print System.out.println(Arrays.toString(midNumList.toArray())); }}输入内容: [3.5, 5.0, 7.0, 5.0, 4.5]
此办法是最简略最根底的解答.
查问了一下其他人的解释, well.. 学习一下.
Leetcode 480.滑动窗口中位数
通过这道题倒是找到Leetcode这个网站, 有很多不错的算法题.