Java实现 LeetCode 480 滑动窗口中位数

超、凢脫俗 2023-07-17 02:51 114阅读 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\]。

提示：

你可以假设 k 始终有效，即：k 始终小于输入的非空数组的元素个数。  
与真实值误差在 10 ^ -5 以内的答案将被视作正确答案。  
PS：  
其实也就是排序，只不过我以后的排序都是二分排序，我的排序数组就是k大小

class Solution { 
           public double[] medianSlidingWindow(int[] nums, int k) { 
            int len = nums.length - k + 1;
            double[] res = new double[len];
            int[] arr = Arrays.copyOfRange(nums, 0, k);
            Arrays.sort(arr);
            for (int i = 0; i < len; i++) { 
                if (k % 2 == 0) { 
                    res[i] = (0.00 + arr[k/2] + arr[k/2-1]) / 2;
                } else { 
                    res[i] = arr[k/2];
                }
                if (i == len - 1) break;
                update(arr, nums[i], nums[i + k]);
            }
            return res;
            
        }
        
        void update(int[] arr, int rm, int add) { 
            if (rm == add) return;
            int idx = Arrays.binarySearch(arr, rm);
            int i = 0;
            if (add > rm) { 
                for (i = idx; i < arr.length - 1; i++) { 
                    if (arr[i+1] >= add) break;
                    arr[i] = arr[i+1];
                }
            } else { 
                for (i = idx; i > 0; i--) { 
                    if (arr[i - 1] <= add) break;
                    arr[i] = arr[i-1];
                }
            }
            arr[i] = add;
        }
    }