dev/democards/problems/problems/480.sliding-window-median.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "source": [
    "Median is the middle value in an ordered integer list. If the size of the list\n",
    "is even, there is no middle value. So the median is the mean of the two middle\n",
    "value.\n",
    "\n",
    "Examples:\n",
    "\n",
    "`[2,3,4]` , the median is `3`\n",
    "\n",
    "`[2,3]`, the median is `(2 + 3) / 2 = 2.5`\n",
    "\n",
    "Given an array _nums_ , there is a sliding window of size _k_ which is moving\n",
    "from the very left of the array to the very right. You can only see the _k_\n",
    "numbers in the window. Each time the sliding window moves right by one\n",
    "position. Your job is to output the median array for each window in the\n",
    "original array.\n",
    "\n",
    "For example,\n",
    "Given _nums_ = `[1,3,-1,-3,5,3,6,7]`, and _k_ = 3.\n",
    "\n",
    "\n",
    "\n",
    "    Window position                Median\n",
    "    ---------------               -----\n",
    "    [1  3  -1] -3  5  3  6  7       1\n",
    "     1 [3  -1  -3] 5  3  6  7       -1\n",
    "     1  3 [-1  -3  5] 3  6  7       -1\n",
    "     1  3  -1 [-3  5  3] 6  7       3\n",
    "     1  3  -1  -3 [5  3  6] 7       5\n",
    "     1  3  -1  -3  5 [3  6  7]      6\n",
    "\n",
    "\n",
    "Therefore, return the median sliding window as `[1,-1,-1,3,5,6]`.\n",
    "\n",
    "**Note:**\n",
    "You may assume `k` is always valid, ie: `k` is always smaller than input\n",
    "array's size for non-empty array.\n",
    "Answers within `10^-5` of the actual value will be accepted as correct."
   ],
   "metadata": {}
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "median_sliding_window (generic function with 1 method)"
     },
     "metadata": {},
     "execution_count": 1
    }
   ],
   "cell_type": "code",
   "source": [
    "# @lc code=start\n",
    "using LeetCode\n",
    "\n",
    "function median_sliding_window(nums::Vector{Int}, k::Int)\n",
    "    tree = AVLTree{Tuple{Int, Int}}()\n",
    "    res = Float64[]\n",
    "    for i in 1:length(nums)\n",
    "        push!(tree, (nums[i], i))\n",
    "        if i ≥ k\n",
    "            push!(res, (tree[k ÷ 2 + 1][1] + tree[(k - 1) ÷ 2 + 1][1]) / 2)\n",
    "            delete!(tree, (nums[i - k + 1], i - k + 1))\n",
    "        end\n",
    "    end\n",
    "    res\n",
    "end\n",
    "# @lc code=end"
   ],
   "metadata": {},
   "execution_count": 1
  },
  {
   "cell_type": "markdown",
   "source": [
    "---\n",
    "\n",
    "*This notebook was generated using [Literate.jl](https://github.com/fredrikekre/Literate.jl).*"
   ],
   "metadata": {}
  }
 ],
 "nbformat_minor": 3,
 "metadata": {
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.10.1"
  },
  "kernelspec": {
   "name": "julia-1.10",
   "display_name": "Julia 1.10.1",
   "language": "julia"
  }
 },
 "nbformat": 4
}