Leetcode: Sliding Window Median
LeetCode window Median
2023-09-11 14:14:07 时间
1 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. 2 3 Examples: 4 [2,3,4] , the median is 3 5 6 [2,3], the median is (2 + 3) / 2 = 2.5 7 8 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. 9 10 For example, 11 Given nums = [1,3,-1,-3,5,3,6,7], and k = 3. 12 13 Window position Median 14 --------------- ----- 15 [1 3 -1] -3 5 3 6 7 1 16 1 [3 -1 -3] 5 3 6 7 -1 17 1 3 [-1 -3 5] 3 6 7 -1 18 1 3 -1 [-3 5 3] 6 7 3 19 1 3 -1 -3 [5 3 6] 7 5 20 1 3 -1 -3 5 [3 6 7] 6 21 Therefore, return the median sliding window as [1,-1,-1,3,5,6].
方法1:Time Complexity O(NK)
暂时只有两个Heap的做法,缺点:In this problem, it is necessary to be able remove elements that are not necessarily at the top of the heap. PriorityQueue has logarithmic time remove top, but a linear time remove arbitrary element.
For a Heap:
remove(): Time Complexity is O(logN)
remove(Object): Time Complexity is O(N)
更好的有multiset的方法,但是还没有看到好的java version的
最大堆的简单定义方法:Collections.reverseOrder(), Returns a comparator that imposes the reverse of the natural ordering on a collection of objects
1 public class Solution { 2 PriorityQueue<Double> high = new PriorityQueue(); 3 PriorityQueue<Double> low = new PriorityQueue(Collections.reverseOrder()); 4 5 6 public double[] medianSlidingWindow(int[] nums, int k) { 7 double[] res = new double[nums.length-k+1]; 8 int index = 0; 9 10 for (int i=0; i<nums.length; i++) { 11 if (i >= k) remove(nums[i-k]); 12 add((double)nums[i]); 13 if (i >= k-1) { 14 res[index++] = findMedian(); 15 } 16 } 17 return res; 18 } 19 20 public void add(double num) { 21 low.offer(num); 22 high.offer(low.poll()); 23 if (low.size() < high.size()) { 24 low.offer(high.poll()); 25 } 26 } 27 28 public double findMedian() { 29 if (low.size() == high.size()) { 30 return (low.peek() + high.peek()) / 2.0; 31 } 32 else return low.peek(); 33 } 34 35 public void remove(double num) { 36 if (num <= findMedian()) { 37 low.remove(num); 38 } 39 else { 40 high.remove(num); 41 } 42 if (low.size() < high.size()) { 43 low.offer(high.poll()); 44 } 45 else if (low.size() > high.size()+1) { 46 high.offer(low.poll()); 47 } 48 } 49 }
相关文章
- Java实现 LeetCode 669 修剪二叉搜索树(遍历树)
- Java实现 LeetCode 521 最长特殊序列 Ⅰ(出题人:“就是喜欢看你们不敢相信那么简单,又不敢提交的样子。”)...
- Java实现 LeetCode 520 检测大写字母
- Java实现 LeetCode 485 最大连续1的个数
- Java实现 LeetCode 421 数组中两个数的最大异或值
- Java实现 LeetCode 543 二叉树的直径
- Java实现 LeetCode 373 查找和最小的K对数字
- Java实现 LeetCode 168 Excel表列名称
- Java实现 LeetCode 136 只出现一次的数字
- Java实现 LeetCode 120 三角形最小路径和
- Java实现 LeetCode 52 N皇后 II
- leetcode 106. 从中序与后序遍历序列构造二叉树
- leetcode - Convert Sorted List to Binary Search Tree
- 【Leetcode刷题Python】LeetCode 478. 在圆内随机生成点
- 【LeetCode】34.在排序数组中查找元素的第一个和最后一个位置