{"id":6597,"date":"2020-04-11T23:02:52","date_gmt":"2020-04-12T06:02:52","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6597"},"modified":"2020-04-13T17:28:09","modified_gmt":"2020-04-14T00:28:09","slug":"leetcode-1409-queries-on-a-permutation-with-key","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/simulation\/leetcode-1409-queries-on-a-permutation-with-key\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1409. Queries on a Permutation With Key"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1409. Queries on a Permutation With Key - \u5237\u9898\u627e\u5de5\u4f5c EP319\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/DwtijVbS3G0?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>\n<\/div><\/figure>\n\n\n\n<p>Given the array&nbsp;<code>queries<\/code>&nbsp;of positive integers between&nbsp;<code>1<\/code>&nbsp;and&nbsp;<code>m<\/code>, you have to process all&nbsp;<code>queries[i]<\/code>&nbsp;(from&nbsp;<code>i=0<\/code>&nbsp;to&nbsp;<code>i=queries.length-1<\/code>) according to the following rules:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>In the beginning, you have the permutation&nbsp;<code>P=[1,2,3,...,m]<\/code>.<\/li><li>For the current&nbsp;<code>i<\/code>, find the position of&nbsp;<code>queries[i]<\/code>&nbsp;in the permutation&nbsp;<code>P<\/code>&nbsp;(<strong>indexing from 0<\/strong>) and then move this at the beginning of the permutation&nbsp;<code>P.<\/code>&nbsp;Notice that the position of&nbsp;<code>queries[i]<\/code>&nbsp;in&nbsp;<code>P<\/code>&nbsp;is the result for&nbsp;<code>queries[i]<\/code>.<\/li><\/ul>\n\n\n\n<p>Return an array containing the result for the given&nbsp;<code>queries<\/code>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> queries = [3,1,2,1], m = 5\n<strong>Output:<\/strong> [2,1,2,1] \n<strong>Explanation:<\/strong> The queries are processed as follow: \nFor i=0: queries[i]=3, P=[1,2,3,4,5], position of 3 in P is <strong>2<\/strong>, then we move 3 to the beginning of P resulting in P=[3,1,2,4,5]. \nFor i=1: queries[i]=1, P=[3,1,2,4,5], position of 1 in P is <strong>1<\/strong>, then we move 1 to the beginning of P resulting in P=[1,3,2,4,5]. \nFor i=2: queries[i]=2, P=[1,3,2,4,5], position of 2 in P is <strong>2<\/strong>, then we move 2 to the beginning of P resulting in P=[2,1,3,4,5]. \nFor i=3: queries[i]=1, P=[2,1,3,4,5], position of 1 in P is <strong>1<\/strong>, then we move 1 to the beginning of P resulting in P=[1,2,3,4,5]. \nTherefore, the array containing the result is [2,1,2,1].  \n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> queries = [4,1,2,2], m = 4\n<strong>Output:<\/strong> [3,1,2,0]\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> queries = [7,5,5,8,3], m = 8\n<strong>Output:<\/strong> [6,5,0,7,5]\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= m &lt;= 10^3<\/code><\/li><li><code>1 &lt;= queries.length &lt;= m<\/code><\/li><li><code>1 &lt;= queries[i] &lt;= m<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution1: Simulation + Hashtable<\/strong><\/h2>\n\n\n\n<p>Use a hashtable to store the location of each key.<br>For each query q, use h[q] to get the index of q, for each key, if its current index is less than q, increase their indices by 1. (move right). Set h[q] to 0.<\/p>\n\n\n\n<p>Time complexity: O(q*m)<br>Space complexity: O(m)<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/04\/1409-ep319-1.png\" alt=\"\" class=\"wp-image-6611\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/04\/1409-ep319-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/04\/1409-ep319-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/04\/1409-ep319-1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\nclass Solution {\npublic:\n  vector<int> processQueries(vector<int>& queries, int m) {\n    vector<int> p(m + 1);\n    iota(begin(p), end(p), -1);\n    vector<int> ans;\n    for (int q : queries) {      \n      ans.push_back(p[q]);\n      for (int i = 1; i <= m; ++i)\n        if (p[i] < p[q]) ++p[i];\n      p[q] = 0;\n    }      \n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: Fenwick Tree + HashTable<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/04\/1409-ep319-2.png\" alt=\"\" class=\"wp-image-6612\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/04\/1409-ep319-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/04\/1409-ep319-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/04\/1409-ep319-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>Time complexity: O(qlogm)<br>Space complexity: O(m)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nclass Fenwick {\npublic:\n  explicit Fenwick(int n): vals_(n) {}\n  \n  \/\/ sum(A[1~i])\n  int query(int i) const {\n    int s = 0;\n    while (i > 0) {\n      s += vals_[i];\n      i -= i & -i;\n    }\n    return s;\n  }\n  \n  \/\/ A[i] += delta\n  void update(int i, int delta) {\n    while (i < vals_.size()) {\n      vals_[i] += delta;\n      i += i &#038; -i;\n    }\n  }\nprivate:\n  vector<int> vals_;\n};\n\nclass Solution {\npublic:\n  vector<int> processQueries(vector<int>& queries, int m) {\n    Fenwick tree(m * 2  + 1);\n    vector<int> pos(m + 1);\n    for (int i = 1; i <= m; ++i)     \n      tree.update(pos[i] = i + m, 1);\n    \n    vector<int> ans;\n    for (int q : queries) {\n      ans.push_back(tree.query(pos[q] - 1));\n      tree.update(pos[q], -1); \/\/ set to 0.      \n      tree.update(pos[q] = m--, 1); \/\/ move to the front.\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\">\nclass Fenwick:\n  def __init__(self, n):\n    self.n = n\n    self.val = [0] * n\n  \n  def query(self, i):\n    s = 0\n    while i > 0:\n      s += self.val[i]\n      i -= i & -i\n    return s\n  \n  def update(self, i, delta):\n    while i < self.n:\n      self.val[i] += delta\n      i += i &#038; -i\n    \nclass Solution:\n  def processQueries(self, queries: List[int], m: int) -> List[int]:    \n    pos = [i + m for i in range(m + 1)]\n    tree = Fenwick(2 * m + 1)\n    for i in range(1, m + 1): tree.update(i + m, 1)    \n    ans = []\n    for q in queries:\n      ans.append(tree.query(pos[q] - 1))\n      tree.update(pos[q], -1)\n      pos[q] = m\n      m -= 1\n      tree.update(pos[q], 1)\n    return ans\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given the array&nbsp;queries&nbsp;of positive integers between&nbsp;1&nbsp;and&nbsp;m, you have to process all&nbsp;queries[i]&nbsp;(from&nbsp;i=0&nbsp;to&nbsp;i=queries.length-1) according to the following rules: In the beginning, you have the permutation&nbsp;P=[1,2,3,&#8230;,m]. For the&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48],"tags":[204,177,582],"class_list":["post-6597","post","type-post","status-publish","format-standard","hentry","category-simulation","tag-fenwick-tree","tag-medium","tag-smulation","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6597","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=6597"}],"version-history":[{"count":8,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6597\/revisions"}],"predecessor-version":[{"id":6614,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6597\/revisions\/6614"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6597"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6597"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6597"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}