专栏首页眯眯眼猫头鹰的小树杈leetcode480. Sliding Window Median

leetcode480. Sliding Window Median

题目要求

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples: [2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Your job is to output the median array for each window in the original array.

For example, Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position                Median
---------------               -----
[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

Therefore, return the median sliding window as [1,-1,-1,3,5,6].

Note: You may assume k is always valid, ie: k is always smaller than input array's size for non-empty array.

假设现在有一个长度为n的整数数组,和长度为k的滑动窗口(k一定小于等于n)。要求找出在每个窗口中的中位数。中位数是指将一组数字按照从小到大排序,位于中间位置上的数值。如果n为奇数,则中位数是第n/2+1个数,否则中位数是第n/2个数和第n/2+1个数的和的平均值。

思路和代码

可以先回顾一下Leetcode上另一个求中位数的题目。这道题目是求一个数据流在任意一个时刻的中位数。这道题目也可以复用那一题的思路。即通过两个优先队列分别始终保存该数组小的一半的所有数字和大的一半的所有数字。只是在这题中需要不断的移出已经不在这个窗口中的数字,并加入新流入窗口的数字。代码如下:

    public double[] medianSlidingWindow(int[] nums, int k) {
        Queue<Integer> small = new PriorityQueue<>(Comparator.reverseOrder());
        Queue<Integer> large = new PriorityQueue<>();

        double[] result = new double[nums.length - k + 1];
        boolean isEven = k % 2 == 0;
        for (int i = 0; i < nums.length; i++) {
            large.offer(nums[i]);
            small.offer(large.poll());
            if (large.size() < small.size()) {
                large.offer(small.poll());
            }
            if (small.size() + large.size() < k) {
                continue;
            }

            double median = isEven ? ((double) large.peek() + (double) small.peek()) / 2.0 : (double) large.peek();
            result[i - k + 1] = median;
            if (large.peek() <= nums[i - k + 1]) {
                large.remove(nums[i - k + 1]);
            } else {
                small.remove(nums[i - k + 1]);
            }
        }
        return result;
    }

在最优解中还有另一种思路。而这种思路理论上也是这题最直观的思路。其实这题一共有三个诉求,即快速的在一个有序的数据结构中写入和删除数据,并且能够快速的在有序的数据结构中找到第k个元素。因此我们可以通过一个二叉查找树来实现在lgN的时间内找到第k个元素,并插入/删除某一个值的元素。它通过在二叉查找树的每一个节点记录左子树的节点个数,来帮助快速定位位于有序数组中第k个元素的位置。

    Node root;

    public double[] medianSlidingWindow(int[] nums, int k) {
        if (nums.length == 0)
            return new double[0];
        if (k == 1) {
            double[] medians = new double[nums.length];
            for (int i = 0; i < nums.length; ++i)
                medians[i] = (double) nums[i];
            return medians;
        }
        double[] medians = new double[nums.length - k + 1];

        for (int i = 0; i < k; ++i) {
            insert(nums[i]);
        }

        if (k % 2 == 1) {
            medians[0] = (double) search(root, k / 2 + 1, 0);
        } else {
            medians[0] = ((double) search(root, k / 2, 0) + (double) search(root, k / 2 + 1, 0)) / 2;
        }

        for (int i = k; i < nums.length; ++i) {
            delete(root, nums[i - k]);
            insert(nums[i]);
            if (k % 2 == 1) {
                medians[i - k + 1] = (double) search(root, k / 2 + 1, 0);
            } else {
                medians[i - k + 1] = ((double) search(root, k / 2, 0) + (double) search(root, k / 2 + 1, 0)) / 2;
            }
        }

        return medians;
    }

    private static class Node {
        int key;
        int cnt;
        int leftSize;
        Node left;
        Node right;

        public Node(int k) {
            key = k;
            cnt = 1;
            leftSize = 0;
            left = null;
            right = null;
        }
    }

    private void insert(int k) {
        Node x = root;
        if (x == null) {
            root = new Node(k);
            return;
        }
        while (true) {
            if (x.key == k) {
                x.cnt++;
                return;
            } else if (x.key > k) {
                x.leftSize++;
                if (x.left == null) {
                    x.left = new Node(k);
                    return;
                }
                x = x.left;
            } else {
                if (x.right == null) {
                    x.right = new Node(k);
                    return;
                }
                x = x.right;
            }
        }
    }

    private void delete(Node x, int k) {
        if (x == null)
            return;
        if (x.key == k) {
            x.cnt--;
        } else if (k < x.key) {
            x.leftSize--;
            delete(x.left, k);
        } else {
            delete(x.right, k);
        }
    }

    private int search(Node x, int n, int presum) {
        if (n > x.cnt + x.leftSize + presum)
            return search(x.right, n, x.cnt + x.leftSize + presum);
        else if (n > x.leftSize + presum)
            return x.key;
        else
            return search(x.left, n, presum);
    }
    public static void main(String[] args) {
        SlidingWindowMedian_480 s = new SlidingWindowMedian_480();
        s.medianSlidingWindow(
                new int[] {1,3,-1,-3,5,3,6,7}, 3);
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode363. Max Sum of Rectangle No Larger Than K

    现有一个由整数构成的矩阵,问从中找到一个子矩阵,要求该子矩阵中各个元素的和为不超过k的最大值,问子矩阵中元素的和为多少? 注:后面的文章中将使用[左上角顶点坐标...

    眯眯眼的猫头鹰
  • 395. Longest Substring with At Least K Repeating Characters

    这是一个经典的分治法解决的问题,关键在于我们如何将这个问题分解为更小的子问题。反过来想,这个子字符串一定不包含什么元素呢?当一个元素出现的总次数小于k,那么该元...

    眯眯眼的猫头鹰
  • leetcode502. IPO

    Suppose LeetCode will start its IPO soon. In order to sell a good price of its s...

    眯眯眼的猫头鹰
  • Array - 164. Maximum Gap

    Given an unsorted array, find the maximum difference between the successive elem...

    用户5705150
  • 信息竞赛进阶指南--搜索相关(模板)

    风骨散人Chiam
  • 微信会被封?!包子 Leetcode 1512 solution Number of Good Pairs

    包子君讲解的leetcode题目是越来越简单,在标题党的路上确实越走越远,对不起包子粉了?

    包子面试培训
  • 洛谷P3355 骑士共存问题

    题目描述 在一个 n*n个方格的国际象棋棋盘上,马(骑士)可以攻击的棋盘方格如图所示。棋盘上某些方格设置了障碍,骑士不得进入 ? 对于给定的 n*n 个方格的国...

    attack
  • LeetCode 477 Total Hamming Distance

    The Hamming distance between two integers is the number of positions at which th...

    Yano_nankai
  • 算法篇:求1的个数

    https://leetcode-cn.com/problems/number-of-1-bits/

    灰子学技术
  • 51Nod-1637-幸运数字转换

    ACM模版 描述 ? 题解 image.png 代码 #include <iostream> #include <queue> using namespace...

    f_zyj

扫码关注云+社区

领取腾讯云代金券