{"id":243,"date":"2017-09-12T01:01:52","date_gmt":"2017-09-12T08:01:52","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=243"},"modified":"2018-07-10T18:52:42","modified_gmt":"2018-07-11T01:52:42","slug":"leetcode-295-find-median-from-data-stream","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/leetcode\/leetcode-295-find-median-from-data-stream\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 295. Find Median from Data Stream O(logn) + O(1)"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 295. Find Median from Data Stream - \u5237\u9898\u627e\u5de5\u4f5c EP51\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/60xnYZ21Ir0?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><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>\u00a0, the median is\u00a0<code>3<\/code><\/p>\n<p><code>[2,3]<\/code>, the median is\u00a0<code>(2 + 3) \/ 2 = 2.5<\/code><\/p>\n<p>Design a data structure that supports the following two operations:<\/p>\n<ul>\n<li>void addNum(int num) &#8211; Add a integer number from the data stream to the data structure.<\/li>\n<li>double findMedian() &#8211; Return the median of all elements so far.<\/li>\n<\/ul>\n<p>For example:<\/p>\n<pre class=\"\">addNum(1)\r\naddNum(2)\r\nfindMedian() = 1.5\r\naddNum(3) \r\nfindMedian() = 2<\/pre>\n<p>&nbsp;<\/p>\n<p><strong>Idea<\/strong>:<\/p>\n<ol>\n<li>Min\/Max heap<\/li>\n<li>Balanced binary search tree<\/li>\n<\/ol>\n<p><a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/295-ep51-1.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-248\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/295-ep51-1.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/295-ep51-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/295-ep51-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/295-ep51-1-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/295-ep51-1-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-247\" style=\"font-size: 1rem;\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/295-ep51-2.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/295-ep51-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/295-ep51-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/295-ep51-2-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/295-ep51-2-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/295-ep51-3.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-246\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/295-ep51-3.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/295-ep51-3.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/295-ep51-3-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/295-ep51-3-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/295-ep51-3-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/p>\n<p><strong>Time Complexity<\/strong>:<\/p>\n<p>add(num): O(logn)<\/p>\n<p>findMedian(): O(logn)<\/p>\n<p><strong>Solution1<\/strong>:<\/p>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running Time: 152 ms\r\nclass MedianFinder {\r\npublic:\r\n    \/** initialize your data structure here. *\/\r\n    MedianFinder() {}\r\n    \r\n    \/\/ l_.size() &gt;= r_.size()\r\n    void addNum(int num) {\r\n        if (l_.empty() || num &lt;= l_.top()) {\r\n            l_.push(num);\r\n        } else {\r\n            r_.push(num);\r\n        }\r\n        \r\n        \/\/ Step 2: Balence left\/right\r\n        if (l_.size() &lt; r_.size()) {\r\n            l_.push(r_.top());\r\n            r_.pop();\r\n        } else if (l_.size() - r_.size() == 2) {\r\n            r_.push(l_.top());\r\n            l_.pop();\r\n        }\r\n    }\r\n    \r\n    double findMedian() {\r\n        if (l_.size() &gt; r_.size()) {\r\n            return static_cast&lt;double&gt;(l_.top());\r\n        } else {            \r\n            return (static_cast&lt;double&gt;(l_.top()) + r_.top()) \/ 2;\r\n        }\r\n    }\r\nprivate:\r\n    priority_queue&lt;int, vector&lt;int&gt;, less&lt;int&gt;&gt; l_;    \/\/ max-heap\r\n    priority_queue&lt;int, vector&lt;int&gt;, greater&lt;int&gt;&gt; r_; \/\/ min-heap\r\n};<\/pre>\n<p>&nbsp;<\/p>\n<p><strong>Solution 2:<\/strong><\/p>\n<pre class=\"lang:c++ decode:true  \">\/\/ Author: Huahua\r\n\/\/ Running time: 172 ms\r\nclass MedianFinder {\r\npublic:\r\n    \/** initialize your data structure here. *\/\r\n    MedianFinder(): l_(m_.cend()), r_(m_.cend()) {}\r\n    \r\n    \/\/ O(logn)\r\n    void addNum(int num) {\r\n        if (m_.empty()) {\r\n            l_ = r_ = m_.insert(num);\r\n            return;\r\n        }\r\n        \r\n        m_.insert(num);\r\n        const size_t n = m_.size();    \r\n        \r\n        if (n &amp; 1) {\r\n            \/\/ odd number\r\n            if (num &gt;= *r_) {         \r\n                l_ = r_;\r\n            } else {\r\n                \/\/ num &lt; *r_, l_ could be invalidated\r\n                l_ = --r_;\r\n            }\r\n        } else {\r\n            if (num &gt;= *r_)\r\n                ++r_;\r\n            else\r\n                --l_;\r\n        }\r\n    }\r\n    \/\/ O(1)\r\n    double findMedian() {\r\n        return (static_cast&lt;double&gt;(*l_) + *r_) \/ 2;\r\n    }\r\nprivate:\r\n    multiset&lt;int&gt; m_;\r\n    multiset&lt;int&gt;::const_iterator l_;  \/\/ current left median\r\n    multiset&lt;int&gt;::const_iterator r_;  \/\/ current right median\r\n};<\/pre>\n<p>&nbsp;<\/p>\n<p><strong>Related Problems<\/strong><\/p>\n<ul>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/difficulty\/hard\/leetcode-480-sliding-window-median\/\">\u82b1\u82b1\u9171 LeetCode 480. Sliding Window Median<\/a><\/li>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/binary-search\/leetcode-4-median-of-two-sorted-arrays\/\">[\u89e3\u9898\u62a5\u544a] LeetCode 4. Median of Two Sorted Arrays<\/a><\/li>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/zoj\/zoj-3612-median\/\">[ZOJ] 3612: Median<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Problem: Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[89,71,3,45],"tags":[74,217,73,11,75,72,90],"class_list":["post-243","post","type-post","status-publish","format-standard","hentry","category-data-structure","category-heap","category-leetcode","category-tree","tag-bst","tag-hard","tag-heap","tag-median","tag-online","tag-priority-queue","tag-stream","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/243","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=243"}],"version-history":[{"count":9,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/243\/revisions"}],"predecessor-version":[{"id":3075,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/243\/revisions\/3075"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=243"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=243"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=243"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}