美文网首页算法
480. 滑动窗口中位数

480. 滑动窗口中位数

作者: 红树_ | 来源:发表于2023-05-15 17:23 被阅读0次

    爱心献给孩子,诚心送给家长,信心留给自己。

    参考480. 滑动窗口中位数

    题目

    中位数是有序序列最中间的那个数。如果序列的长度是偶数,则没有最中间的数;此时中位数是最中间的两个数的平均数。例如:

    • [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,-1,-1,3,5,6]

    解题思路

    • 二分查找:使用二分查找维护一个有序列表的插入和删除,对于有序列表的中位数计算就很方便简单了。

    二分查找

    class Solution {
        private List<Integer> window;
        public double[] medianSlidingWindow(int[] nums, int k) {
            int n = nums.length;
            double[] ans = new double[n - k + 1];
            window = new ArrayList<>();
            for(int i = 0; i < k; i++) window.add(nums[i]);
            Collections.sort(window);
            if (k%2 == 0) ans[0] = window.get(k / 2 - 1) / 2.0 + window.get(k / 2) / 2.0;
            else ans[0] = window.get(k / 2);
            for (int i = 1; i + k -1 < n; i ++) {
                if(nums[i-1] != nums[i+k-1]){
                    remove(nums[i-1]);
                    insert(nums[i+k-1]);
                }
                if (k%2 == 0)ans[i] = window.get(k/2 - 1) / 2.0 + window.get(k / 2) / 2.0;
                else ans[i] = window.get(k / 2);
                    
            }       
            return ans;
        }
        private void insert(int val) {
            int left = 0;
            int right = window.size()-1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (window.get(mid) < val) {
                    left = mid + 1;
                }
                else {
                    right = mid - 1;
                }
            }
            window.add(left, val);
        }
        private void remove(int val) {
            int left = 0;
            int right = window.size() - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (window.get(mid) < val) {
                    left = mid + 1;
                }
                else if (window.get(mid) > val) {
                    right = mid - 1;
                }
                else {
                    window.remove(mid);
                    return;
                }
            }
        }
    }
    

    复杂度分析

    • 时间复杂度:O(nlogk),添加和删除操作(二分)logk,k为滑动窗口长度,n为数组nums长度。
    • 空间复杂度:O(k),列表长度即滑动窗口长度。

    相关文章

      网友评论

        本文标题:480. 滑动窗口中位数

        本文链接:https://www.haomeiwen.com/subject/emtvsdtx.html