{"id":1672,"date":"2018-01-28T00:56:53","date_gmt":"2018-01-28T08:56:53","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=1672"},"modified":"2019-09-29T21:38:14","modified_gmt":"2019-09-30T04:38:14","slug":"leetcode-480-sliding-window-median","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/difficulty\/hard\/leetcode-480-sliding-window-median\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 480. Sliding Window Median"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 480. Sliding Window Median - \u5237\u9898\u627e\u5de5\u4f5c EP162\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/kDS6ScZwNnI?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<p>\u9898\u76ee\u5927\u610f\uff1a\u8ba9\u4f60\u6c42\u79fb\u52a8\u7a97\u53e3\u7684\u4e2d\u4f4d\u6570\u3002<\/p>\n<p><strong>Problem:<\/strong><\/p>\n<p>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.<\/p>\n<p>Examples:<\/p>\n<p><code>[2,3,4]<\/code>&nbsp;, the median is&nbsp;<code>3<\/code><\/p>\n<p><code>[2,3]<\/code>, the median is&nbsp;<code>(2 + 3) \/ 2 = 2.5<\/code><\/p>\n<p>Given an array&nbsp;<i>nums<\/i>, there is a sliding window of size&nbsp;<i>k<\/i>&nbsp;which is moving from the very left of the array to the very right. You can only see the&nbsp;<i>k<\/i>&nbsp;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.<\/p>\n<p>For example,<br \/>\nGiven&nbsp;<i>nums<\/i>&nbsp;=&nbsp;<code>[1,3,-1,-3,5,3,6,7]<\/code>, and&nbsp;<i>k<\/i>&nbsp;= 3.<\/p>\n<pre>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<\/pre>\n<p>Therefore, return the median sliding window as&nbsp;<code>[1,-1,-1,3,5,6]<\/code>.<\/p>\n<p><b>Note:&nbsp;<\/b><br \/>\nYou may assume&nbsp;<code>k<\/code>&nbsp;is always valid, ie:&nbsp;<code>k<\/code>&nbsp;is always smaller than input array&#8217;s size for non-empty array.<\/p>\n<p><script async=\"\" src=\"https:\/\/pagead2.googlesyndication.com\/pagead\/js\/adsbygoogle.js\"><\/script><br \/>\n<ins class=\"adsbygoogle\" style=\"display:block\" data-ad-format=\"fluid\" data-ad-layout-key=\"-fb+5w+4e-db+86\" data-ad-client=\"ca-pub-2404451723245401\" data-ad-slot=\"2162692788\"><\/ins><br \/>\n<script><br \/>\n     (adsbygoogle = window.adsbygoogle || []).push({});<br \/>\n<\/script><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1695\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/480-ep162-0.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/480-ep162-0.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/480-ep162-0-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/480-ep162-0-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1696\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/480-ep162-2.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/480-ep162-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/480-ep162-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/480-ep162-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1698\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/480-ep162-2-1.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/480-ep162-2-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/480-ep162-2-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/480-ep162-2-1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<p><strong>Solution 0: Brute Force<\/strong><\/p>\n<p>Time complexity: O(n*klogk) TLE 32\/42 test cases passed<\/p>\n<p><b>Solution 1: Insertion&nbsp;Sort<\/b><\/p>\n<p>Time complexity: O(k*logk +&nbsp; (n &#8211; k + 1)*k)<\/p>\n<p>Space complexity: O(k)<\/p>\n<p>C++ \/ vector<\/p>\n<pre class=\"lang:default decode:true \">\/\/ Author: Huahua\n\/\/ Running time: 99 ms\nclass Solution {\npublic:\n  vector&lt;double&gt; medianSlidingWindow(vector&lt;int&gt;&amp; nums, int k) {    \n    vector&lt;double&gt; ans;\n    if (k == 0) return ans;\n    vector&lt;int&gt; window(nums.begin(), nums.begin() + k - 1);\n    std::sort(window.begin(), window.end());\n    for (int i = k - 1; i &lt; nums.size(); ++i) {\n      window.push_back(nums[i]);\n      auto it = prev(window.end(), 1);\n      auto const insertion_point = \n              std::upper_bound(window.begin(), it, *it);      \n      std::rotate(insertion_point, it, it + 1);          \n      ans.push_back((static_cast&lt;double&gt;(window[k \/ 2]) + window[(k - 1) \/ 2]) \/ 2);\n      window.erase(std::find(window.begin(), window.end(), nums[i - k + 1]));      \n    }\n    return ans;\n  }\n};<\/pre>\n<p>C++ \/ vector + binary_search for deletion.<\/p>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\n\/\/ Running time: 84 ms\nclass Solution {\npublic:\n  vector&lt;double&gt; medianSlidingWindow(vector&lt;int&gt;&amp; nums, int k) {    \n    vector&lt;double&gt; ans;\n    if (k == 0) return ans;\n    vector&lt;int&gt; window(nums.begin(), nums.begin() + k - 1);\n    std::sort(window.begin(), window.end());\n    for (int i = k - 1; i &lt; nums.size(); ++i) {\n      window.push_back(nums[i]);\n      auto it = prev(window.end(), 1);\n      auto const insertion_point = \n              std::upper_bound(window.begin(), it, *it);      \n      std::rotate(insertion_point, it, it + 1);          \n      ans.push_back((static_cast&lt;double&gt;(window[k \/ 2]) + window[(k - 1) \/ 2]) \/ 2);\n      window.erase(std::lower_bound(window.begin(), window.end(), nums[i - k + 1]));      \n    }\n    return ans;\n  }\n};<\/pre>\n<p>Java<\/p>\n<pre class=\"lang:java decode:true \">\/\/ Author: Huahua\n\/\/ Running time: 60 ms\nclass Solution {\n  public double[] medianSlidingWindow(int[] nums, int k) {\n    if (k == 0) return new double[0];\n    double[] ans = new double[nums.length - k + 1];\n    int[] window = new int[k];\n    for (int i = 0; i &lt; k; ++i) \n      window[i] = nums[i];\n    Arrays.sort(window);\n    for (int i = k; i &lt;= nums.length; ++i) {\n      ans[i - k] = ((double)window[k \/ 2] + window[(k - 1)\/2]) \/ 2;\n      if (i == nums.length) break;\n      remove(window, nums[i - k]);\n      insert(window, nums[i]);\n    }\n    return ans;\n  }\n  \n  \/\/ Insert val into window, window[k - 1] is empty before inseration\n  private void insert(int[] window, int val) {\n    int i = 0;\n    while (i &lt; window.length - 1 &amp;&amp; val &gt; window[i]) ++i;\n    int j = window.length - 1;\n    while (j &gt; i) window[j] = window[--j];\n    window[j] = val;\n  }\n  \n  \/\/ Remove val from window and shrink it.\n  private void remove(int[] window, int val) {\n    int i = 0;\n    while (i &lt; window.length &amp;&amp; val != window[i]) ++i;\n    while (i &lt; window.length - 1) window[i] = window[++i];\n  }\n}<\/pre>\n<p>Java \/ Binary Search<\/p>\n<pre class=\"lang:default decode:true \">\/\/ Author: Huahua\n\/\/ Running time: 47 ms (&lt;98.96%)\nclass Solution {\n  public double[] medianSlidingWindow(int[] nums, int k) {\n    if (k == 0) return new double[0];\n    double[] ans = new double[nums.length - k + 1];\n    int[] window = new int[k];\n    for (int i = 0; i &lt; k; ++i) \n      window[i] = nums[i];\n    Arrays.sort(window);\n    for (int i = k; i &lt;= nums.length; ++i) {\n      ans[i - k] = ((double)window[k \/ 2] + window[(k - 1)\/2]) \/ 2;\n      if (i == nums.length) break;\n      remove(window, nums[i - k]);\n      insert(window, nums[i]);\n    }\n    return ans;\n  }\n  \n  \/\/ Insert val into window, window[k - 1] is empty before inseration\n  private void insert(int[] window, int val) {\n    int i = Arrays.binarySearch(window, val);\n    if (i &lt; 0) i = - i - 1;    \n    int j = window.length - 1;\n    while (j &gt; i) window[j] = window[--j];\n    window[j] = val;\n  }\n  \n  \/\/ Remove val from window and shrink it.\n  private void remove(int[] window, int val) {\n    int i = Arrays.binarySearch(window, val);\n    while (i &lt; window.length - 1) window[i] = window[++i];\n  }\n  \n  \n}<\/pre>\n<p>&nbsp;<\/p>\n<p>Python<\/p>\n<pre class=\"lang:python decode:true \">\"\"\"\nAuthor: Huahua\nRunning time: 161 ms (&lt; 93.75%)\n\"\"\"\nclass Solution:\n  def medianSlidingWindow(self, nums, k):\n    if k == 0: return []\n    ans = []\n    window = sorted(nums[0:k])\n    for i in range(k, len(nums) + 1):\n      ans.append((window[k \/\/ 2] + window[(k - 1) \/\/ 2]) \/ 2.0)\n      if i == len(nums): break\n      index = bisect.bisect_left(window, nums[i - k])\n      window.pop(index)      \n      bisect.insort_left(window, nums[i])\n    return ans\n<\/pre>\n<p><strong>Solution 2: BST<\/strong><\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\n\/\/ Running time: 68 ms\nclass Solution {\npublic:\n  vector&lt;double&gt; medianSlidingWindow(vector&lt;int&gt;&amp; nums, int k) {    \n    vector&lt;double&gt; ans;\n    if (k == 0) return ans;\n    multiset&lt;int&gt; window(nums.begin(), nums.begin() + k);\n    auto mid = next(window.begin(), (k - 1) \/ 2);    \n    for (int i = k; i &lt;= nums.size(); ++i) {\n      ans.push_back((static_cast&lt;double&gt;(*mid) + \n                     *next(mid, (k + 1) % 2)) \/ 2.0);\n      if (i == nums.size()) break;\n      \n      window.insert(nums[i]);\n      if (nums[i] &lt; *mid) --mid; \n      if (nums[i - k] &lt;= *mid) ++mid;\n      window.erase(window.lower_bound(nums[i - k])); \n    }\n    return ans;\n  }\n};<\/pre>\n<p>&nbsp;<\/p>\n<p><strong>Related Problems:<\/strong><\/p>\n<ul>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/leetcode\/leetcode-295-find-median-from-data-stream\/\">[\u89e3\u9898\u62a5\u544a] LeetCode 295. Find Median from Data Stream O(logn) + O(1)<\/a><\/li>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/heap\/leetcode-239-sliding-window-maximum\/\">\u82b1\u82b1\u9171 LeetCode 239. Sliding Window Maximum<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u76ee\u5927\u610f\uff1a\u8ba9\u4f60\u6c42\u79fb\u52a8\u7a97\u53e3\u7684\u4e2d\u4f4d\u6570\u3002 Problem: Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value.&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[184,165],"tags":[52,11,215,15],"class_list":["post-1672","post","type-post","status-publish","format-standard","hentry","category-array","category-hard","tag-binary-search","tag-median","tag-sliding-window","tag-sorting","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1672","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=1672"}],"version-history":[{"count":17,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1672\/revisions"}],"predecessor-version":[{"id":5634,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1672\/revisions\/5634"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=1672"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=1672"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=1672"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}