```C++ []\nclass Solution {\npublic:\n vector medianSlidingWindow(vector& nums, int k) {\n vector medians;\n unordered_map hashTable;\n priority_queue lo;\n priority_queue, greater> hi;\n\n int i = 0;\n\n while(i < k){\n lo.push(nums[i++]);\n }\n for(int j = 0; j < k / 2; ++j){\n hi.push(lo.top());\n lo.pop();\n }\n\n while(true){\n medians.push_back(k & 1 ? lo.top() : ((double)lo.top() + (double)hi.top()) * 0.5);\n\n if(i >= nums.size()) break;\n\n int outNum = nums[i - k];\n int inNum = nums[i++];\n int balance = 0;\n\n balance += outNum <= lo.top() ? -1 : 1;\n hashTable[outNum]++;\n\n if(!lo.empty() && inNum <= lo.top()){\n balance++;\n lo.push(inNum);\n }\n else{\n balance--;\n hi.push(inNum);\n }\n\n if(balance < 0){\n lo.push(hi.top());\n hi.pop();\n balance++;\n }\n if(balance > 0){\n hi.push(lo.top());\n lo.pop();\n balance--;\n }\n\n while(hashTable[lo.top()]){\n hashTable[lo.top()]--;\n lo.pop();\n }\n\n while(!hi.empty() && hashTable[hi.top()]){\n hashTable[hi.top()]--;\n hi.pop();\n }\n }\n return medians;\n }\n};\n```\n\n```Python3 []\nclass Solution:\n def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n if k == 1:\n return nums\n if k == 2:\n return [(p + q) / 2 for p,q in pairwise(nums)]\n kodd = k % 2\n ref = sorted(nums[:k])\n hl = [-x for x in ref[:k//2]]\n hl.reverse()\n hr = ref[k//2:]\n if kodd:\n out = [hr[0]]\n else:\n out = [(hr[0] - hl[0]) / 2]\n hrd = []\n hld = []\n def cleanr():\n while hrd and hrd[0] == hr[0]:\n heappop(hrd)\n heappop(hr)\n def cleanl():\n while hld and hld[0] == hl[0]:\n heappop(hld)\n heappop(hl)\n for idx,x in enumerate(nums[k:]):\n y = nums[idx]\n mid = hr[0]\n if y >= mid:\n if x < mid:\n x = -heappushpop(hl, -x)\n cleanl()\n heappush(hr, x)\n heappush(hrd, y)\n cleanr()\n else:\n if x >= mid:\n x = heappushpop(hr, x)\n cleanr()\n heappush(hl, -x)\n heappush(hld, -y)\n cleanl()\n if kodd:\n out.append(hr[0])\n else:\n out.append((hr[0] - hl[0]) / 2)\n return out\n```\n\n```Java []\nclass Solution {\n public double[] medianSlidingWindow(int[] nums, int k) {\n if (nums == null || nums.length == 0)\n return new double[0];\n \n Node root = null;\n for (int i = 0; i < k; i++) {\n root = insert(root, nums[i]);\n }\n \n double[] r = new double[nums.length - k + 1];\n boolean even = k % 2 == 0;\n int j = 0;\n for (int i = k; i <= nums.length; i++) {\n double sum = 0.0;\n if (even)\n sum = (findSmallest(root, k/2).val + findSmallest(root, k/2 + 1).val) / 2.0;\n else\n sum = findSmallest(root, k/2 + 1).val;\n r[j++] = sum;\n if (i < nums.length) {\n root = insert(root, nums[i]);\n root = delete(root, nums[i - k]);\n }\n }\n \n return r;\n }\n \n private Node findSmallest(Node root, int k) {\n int s = countWith(root.left) + 1;\n if (s == k)\n return root;\n if (s > k) {\n return findSmallest(root.left, k);\n }\n return findSmallest(root.right, k - s);\n } \n \n private Node delete(Node root, long val) {\n if (root == null)\n return null;\n else if (val > root.val) \n root.right = delete(root.right, val);\n else if (val < root.val)\n root.left = delete(root.left, val);\n else {\n if (root.left == null)\n root = root.right;\n else if (root.right == null)\n root = root.left;\n else {\n Node t = findMin(root.right);\n root.val = t.val;\n root.right = delete(root.right, t.val);\n }\n }\n \n return updateNode(root);\n }\n \n private Node findMin(Node root) {\n if (root.left != null)\n return findMin(root.left);\n return root;\n }\n\n private Node insert(Node root, long val)\n {\n if (root == null)\n {\n return new Node(val);\n }\n if (val >= root.val)\n {\n root.right = insert(root.right, val);\n }\n else\n {\n root.left = insert(root.left, val);\n }\n \n return updateNode(root);\n }\n \n private Node updateNode(Node root) {\n int b = balance(root); \t\t\n if (b == 2 && balance(root.left) < 0)\n {\n root.left = leftRotate(root.left);\n root = rightRotate(root);\n }\n else if (b == -2 && balance(root.right) > 0)\n {\n root.right = rightRotate(root.right);\n root = leftRotate(root);\n }\n else if (b == 2)\n {\n root = rightRotate(root);\n }\n else if (b == -2)\n {\n root = leftRotate(root);\n }\n update(root);\n return root;\n }\n\n private Node leftRotate(Node n)\n {\n Node r = n.right;\n n.right = r.left;\n r.left = n;\n update(n);\n update(r);\n return r;\n }\n\n private Node rightRotate(Node n)\n {\n Node l = n.left;\n n.left = l.right;\n l.right = n;\n update(n);\n update(l);\n return l;\n }\n\n private int balance(Node n)\n {\n if (n==null)return 0;\n return height(n.left) - height(n.right);\n }\n\n private void update(Node n)\n {\n if (n==null)return;\n n.height = Math.max(height(n.left), height(n.right)) + 1;\n n.count = n.left != null ? n.left.count + 1 : 0;\n n.count += n.right != null ? n.right.count + 1 : 0;\n }\n\n private int height(Node n)\n {\n return n != null ? n.height : 0;\n }\n\n private int countWith(Node n)\n {\n return n != null ? n.count + 1 : 0;\n }\n\n static class Node\n {\n Node left;\n Node right;\n long val;\n int count;\n int height;\n\n Node(long val)\n {\n this.val = val;\n }\n }\n}\n```\n

Sliding Window Median

Problem Description

Problem Description

Answer Panel