{"id":8350,"date":"2021-04-13T19:58:09","date_gmt":"2021-04-14T02:58:09","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8350"},"modified":"2021-04-13T20:02:22","modified_gmt":"2021-04-14T03:02:22","slug":"leetcode-1825-finding-mk-average","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/data-structure\/leetcode-1825-finding-mk-average\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1825. Finding MK Average"},"content":{"rendered":"\n

You are given two integers, m<\/code> and k<\/code>, and a stream of integers. You are tasked to implement a data structure that calculates the MKAverage<\/strong> for the stream.<\/p>\n\n\n\n

The MKAverage<\/strong> can be calculated using these steps:<\/p>\n\n\n\n

  1. If the number of the elements in the stream is less than m<\/code> you should consider the MKAverage<\/strong> to be -1<\/code>. Otherwise, copy the last m<\/code> elements of the stream to a separate container.<\/li>
  2. Remove the smallest k<\/code> elements and the largest k<\/code> elements from the container.<\/li>
  3. Calculate the average value for the rest of the elements rounded down to the nearest integer<\/strong>.<\/li><\/ol>\n\n\n\n

    Implement the MKAverage<\/code> class:<\/p>\n\n\n\n

    • MKAverage(int m, int k)<\/code> Initializes the MKAverage<\/strong> object with an empty stream and the two integers m<\/code> and k<\/code>.<\/li>
    • void addElement(int num)<\/code> Inserts a new element num<\/code> into the stream.<\/li>
    • int calculateMKAverage()<\/code> Calculates and returns the MKAverage<\/strong> for the current stream rounded down to the nearest integer<\/strong>.<\/li><\/ul>\n\n\n\n

      Example 1:<\/strong><\/p>\n\n\n\n

      Input<\/strong>\n[\"MKAverage\", \"addElement\", \"addElement\", \"calculateMKAverage\", \"addElement\", \"calculateMKAverage\", \"addElement\", \"addElement\", \"addElement\", \"calculateMKAverage\"]\n[[3, 1], [3], [1], [], [10], [], [5], [5], [5], []]\nOutput<\/strong>\n[null, null, null, -1, null, 3, null, null, null, 5]\n
      Explanation<\/strong> MKAverage obj = new MKAverage(3, 1); obj.addElement(3); \/\/ current elements are [3] obj.addElement(1); \/\/ current elements are [3,1] obj.calculateMKAverage(); \/\/ return -1, because m = 3 and only 2 elements exist. obj.addElement(10); \/\/ current elements are [3,1,10] obj.calculateMKAverage(); \/\/ The last 3 elements are [3,1,10]. \/\/ After removing smallest and largest 1 element the container will be [3]. \/\/ The average of [3] equals 3\/1 = 3, return 3 obj.addElement(5); \/\/ current elements are [3,1,10,5] obj.addElement(5); \/\/ current elements are [3,1,10,5,5] obj.addElement(5); \/\/ current elements are [3,1,10,5,5,5] obj.calculateMKAverage(); \/\/ The last 3 elements are [5,5,5]. \/\/ After removing smallest and largest 1 element the container will be [5]. \/\/ The average of [5] equals 5\/1 = 5, return 5<\/code><\/code><\/p>\n<\/pre>\n\n\n\n
      Constraints:<\/strong><\/p>\n\n\n\n
      • 3 <= m <= 105<\/sup><\/code><\/li>
      • 1 <= k*2 < m<\/code><\/li>
      • 1 <= num <= 105<\/sup><\/code><\/li>
      • At most 105<\/sup><\/code> calls will be made to addElement<\/code> and calculateMKAverage<\/code>.<\/li><\/ul>\n\n\n\n
        Solution 1: Multiset * 3<\/strong><\/h2>\n\n\n\n
        Use three multiset to track the left part (smallest k elements), right part (largest k elements) and mid (middle part of m – 2*k elements).<\/p>\n\n\n\n
        Time complexity: addElememt: O(logn), average: O(1)
        Space complexity: O(n)<\/p>\n\n\n\n
        \n
        C++<\/h2>\n
        \n\n
        \nclass MKAverage {\npublic:\n  MKAverage(int m, int k): \n    sum(0), m(m), k(k), n(m - 2*k) {}\n\n  void addElement(int num) {\n    if (q.size() == m) {      \n      remove(q.front());\n      q.pop();\n    }\n    q.push(num);\n    add(num);\n  }\n\n  int calculateMKAverage() {    \n    return (q.size() < m) ? -1 : sum \/ n;\n  }\nprivate:\n  void add(int x) {\n    left.insert(x);\n    \n    if (left.size() > k) {\n      auto it = prev(end(left));\n      sum += *it;\n      mid.insert(*it);      \n      left.erase(it);\n    }\n    \n    if (mid.size() > n) {\n      auto it = prev(end(mid));\n      sum -= *it; \n      right.insert(*it);\n      mid.erase(it);\n    }\n  }\n  \n  void remove(int x) {\n    if (x <= *rbegin(left)) {\n      left.erase(left.find(x));\n    } else if (x <= *rbegin(mid)) {\n      sum -= x;\n      mid.erase(mid.find(x));\n    } else {\n      right.erase(right.find(x));\n    }\n    \n    if (left.size() < k) {\n      auto it = begin(mid);\n      sum -= *it;\n      left.insert(*it);\n      mid.erase(it);\n    }\n    \n    if (mid.size() < n) {\n      auto it = begin(right);\n      sum += *it;\n      mid.insert(*it);\n      right.erase(it);\n    }\n  }\n  \n  queue q;\n  multiset left, mid, right;  \n  long sum;\n  const int m;\n  const int k;\n  const int n;\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
        You are given two integers, m and k, and a stream of integers. You are tasked to implement a data structure that calculates the MKAverage for the stream. The MKAverage can be…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[89],"tags":[291,217,335,706],"class_list":["post-8350","post","type-post","status-publish","format-standard","hentry","category-data-structure","tag-data-structure","tag-hard","tag-multiset","tag-ordered-set","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8350","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=8350"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8350\/revisions"}],"predecessor-version":[{"id":8352,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8350\/revisions\/8352"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8350"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8350"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8350"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}