乐趣区

关于算法:算法-滑动窗口中位数

jiezi

问题:

滑动窗口中位数
中位数是有序序列最两头的那个数。如果序列的大小是偶数，则没有最两头的数；此时中位数是最两头的两个数的平均数。例如：[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 这个网站, 有很多不错的算法题.

退出移动版