{"id":1487,"date":"2018-01-03T21:59:12","date_gmt":"2018-01-04T05:59:12","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=1487"},"modified":"2018-08-31T12:47:54","modified_gmt":"2018-08-31T19:47:54","slug":"leetcode-315-count-of-smaller-numbers-after-self","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/array\/leetcode-315-count-of-smaller-numbers-after-self\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 315. Count of Smaller Numbers After Self"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 315. Count of Smaller Numbers After Self - \u5237\u9898\u627e\u5de5\u4f5c EP149\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/2SVLYsq5W8M?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\u7ed9\u4f60\u4e00\u4e2a\u6570\u7ec4\uff0c\u5bf9\u4e8e\u6570\u7ec4\u4e2d\u7684\u6bcf\u4e2a\u5143\u7d20\uff0c\u8fd4\u56de\u4e00\u5171\u6709\u591a\u5c11\u5728\u5b83\u4e4b\u540e\u7684\u5143\u7d20\u6bd4\u5b83\u5c0f\u3002<\/p>\n<p><strong>Problem:<\/strong><\/p>\n<p>You are given an integer array\u00a0<i>nums<\/i>\u00a0and you have to return a new\u00a0<i>counts<\/i>\u00a0array. The\u00a0<i>counts<\/i>\u00a0array has the property where\u00a0<code>counts[i]<\/code>\u00a0is the number of smaller elements to the right of\u00a0<code>nums[i]<\/code>.<\/p>\n<p><b>Example:<\/b><\/p>\n<pre class=\"\">Given nums = [5, 2, 6, 1]\r\n\r\nTo the right of 5 there are 2 smaller elements (2 and 1).\r\nTo the right of 2 there is only 1 smaller element (1).\r\nTo the right of 6 there is 1 smaller element (1).\r\nTo the right of 1 there is 0 smaller element.\r\n<\/pre>\n<p>Return the array\u00a0<code>[2, 1, 1, 0]<\/code>.<\/p>\n<p><strong>Idea:<\/strong><\/p>\n<p>Fenwick Tree \/ Binary Indexed Tree<\/p>\n<p>BST<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1515\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/315-ep149-1.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/315-ep149-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/315-ep149-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/315-ep149-1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1514\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/315-ep149-2.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/315-ep149-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/315-ep149-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/315-ep149-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-1513\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/315-ep149-3.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/315-ep149-3.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/315-ep149-3-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/315-ep149-3-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<h1><strong>Solution 1: Binary Indexed Tree (Fenwick Tree)<\/strong><\/h1>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:default decode:true\">\/\/ Author: Huahua\r\n\/\/ Runnning time: 32 ms\r\n\/\/ Time complexity: O(nlogn)\r\n\/\/ Space complexity: O(k), k is the number unique elements\r\nclass FenwickTree {    \r\npublic:\r\n    FenwickTree(int n): sums_(n + 1, 0) {}\r\n    \r\n    void update(int i, int delta) {\r\n        while (i &lt; sums_.size()) {\r\n            sums_[i] += delta;\r\n            i += lowbit(i);\r\n        }\r\n    }\r\n    \r\n    int query(int i) const {        \r\n        int sum = 0;\r\n        while (i &gt; 0) {\r\n            sum += sums_[i];\r\n            i -= lowbit(i);\r\n        }\r\n        return sum;\r\n    }\r\nprivate:\r\n    static inline int lowbit(int x) { return x &amp; (-x); }\r\n    vector&lt;int&gt; sums_;\r\n};\r\n\r\nclass Solution {\r\npublic:\r\n    vector&lt;int&gt; countSmaller(vector&lt;int&gt;&amp; nums) {\r\n        \/\/ Sort the unique numbers\r\n        set&lt;int&gt; sorted(nums.begin(), nums.end());\r\n        \/\/ Map the number to its rank\r\n        unordered_map&lt;int, int&gt; ranks;\r\n        int rank = 0;\r\n        for (const int num : sorted)\r\n            ranks[num] = ++rank;\r\n        \r\n        vector&lt;int&gt; ans;\r\n        FenwickTree tree(ranks.size());\r\n        \/\/ Scan the numbers in reversed order\r\n        for (int i = nums.size() - 1; i &gt;= 0; --i) {\r\n            \/\/ Chechk how many numbers are smaller than the current number.\r\n            ans.push_back(tree.query(ranks[nums[i]] - 1));\r\n            \/\/ Increse the count of the rank of current number.\r\n            tree.update(ranks[nums[i]], 1);\r\n        }\r\n        \r\n        std::reverse(ans.begin(), ans.end());\r\n        return ans;\r\n    }\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:java decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 28 ms\r\nclass Solution {\r\n  private static int lowbit(int x) { return x &amp; (-x); }\r\n  \r\n  class FenwickTree {    \r\n    private int[] sums;    \r\n    \r\n    public FenwickTree(int n) {\r\n      sums = new int[n + 1];\r\n    }\r\n\r\n    public void update(int i, int delta) {    \r\n      while (i &lt; sums.length) {\r\n          sums[i] += delta;\r\n          i += lowbit(i);\r\n      }\r\n    }\r\n\r\n    public int query(int i) {       \r\n      int sum = 0;\r\n      while (i &gt; 0) {\r\n          sum += sums[i];\r\n          i -= lowbit(i);\r\n      }\r\n      return sum;\r\n    }    \r\n  };\r\n  \r\n  public List&lt;Integer&gt; countSmaller(int[] nums) {\r\n    int[] sorted = Arrays.copyOf(nums, nums.length);\r\n    Arrays.sort(sorted);\r\n    Map&lt;Integer, Integer&gt; ranks = new HashMap&lt;&gt;();\r\n    int rank = 0;\r\n    for (int i = 0; i &lt; sorted.length; ++i)\r\n      if (i == 0 || sorted[i] != sorted[i - 1])\r\n        ranks.put(sorted[i], ++rank);\r\n    \r\n    FenwickTree tree = new FenwickTree(ranks.size());\r\n    List&lt;Integer&gt; ans = new ArrayList&lt;Integer&gt;();\r\n    for (int i = nums.length - 1; i &gt;= 0; --i) {\r\n      int sum = tree.query(ranks.get(nums[i]) - 1);      \r\n      ans.add(tree.query(ranks.get(nums[i]) - 1));\r\n      tree.update(ranks.get(nums[i]), 1);\r\n    }\r\n    \r\n    Collections.reverse(ans);\r\n    return ans;\r\n  }\r\n}<\/pre>\n<\/div><\/div>\n<h1><strong>Solution 2: BST<\/strong><\/h1>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:default decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 26 ms\r\nstruct BSTNode {\r\n    int val;\r\n    int count;\r\n    int left_count;\r\n    BSTNode* left;\r\n    BSTNode* right;    \r\n    BSTNode(int val): val(val), count(1), left_count(0), left{nullptr}, right{nullptr} {}\r\n    ~BSTNode() { delete left; delete right; }\r\n    int less_or_equal() const { return count + left_count; }\r\n};\r\nclass Solution {\r\npublic:\r\n    vector&lt;int&gt; countSmaller(vector&lt;int&gt;&amp; nums) {\r\n        if (nums.empty()) return {};\r\n        std::reverse(nums.begin(), nums.end());\r\n        std::unique_ptr&lt;BSTNode&gt; root(new BSTNode(nums[0]));\r\n        vector&lt;int&gt; ans{0};\r\n        for (int i = 1; i &lt; nums.size(); ++i)\r\n            ans.push_back(insert(root.get(), nums[i]));\r\n        std::reverse(ans.begin(), ans.end());\r\n        return ans;\r\n    }\r\nprivate:\r\n    \/\/ Returns the number of elements smaller than val under root.\r\n    int insert(BSTNode* root, int val) {\r\n        if (root-&gt;val == val) {\r\n            ++root-&gt;count;\r\n            return root-&gt;left_count;\r\n        } else if (val &lt; root-&gt;val) {\r\n            ++root-&gt;left_count;\r\n            if (root-&gt;left == nullptr) {\r\n                root-&gt;left = new BSTNode(val);            \r\n                return 0;\r\n            } \r\n            return insert(root-&gt;left, val);\r\n        } else  {\r\n            if (root-&gt;right == nullptr) {\r\n                root-&gt;right = new BSTNode(val);\r\n                return root-&gt;less_or_equal();\r\n            }\r\n            return root-&gt;less_or_equal() + insert(root-&gt;right, val);\r\n        }\r\n    }\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:java decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 10 ms\r\nclass Solution {\r\n  class Node {\r\n    int val;\r\n    int count;\r\n    int left_count;\r\n    Node left;\r\n    Node right;\r\n    public Node(int val) { this.val = val; this.count = 1; }\r\n    public int less_or_equal() { return count + left_count; }\r\n  }\r\n  \r\n  public List&lt;Integer&gt; countSmaller(int[] nums) {\r\n    List&lt;Integer&gt; ans = new ArrayList&lt;&gt;();\r\n    if (nums.length == 0) return ans;\r\n    int n = nums.length;\r\n    Node root = new Node(nums[n - 1]);\r\n    ans.add(0);\r\n    for (int i = n - 2; i &gt;= 0; --i)\r\n      ans.add(insert(root, nums[i]));\r\n    Collections.reverse(ans);\r\n    return ans;\r\n  }\r\n  \r\n  private int insert(Node root, int val) {\r\n    if (root.val == val) {\r\n      ++root.count;\r\n      return root.left_count;\r\n    } else if (val &lt; root.val) {\r\n      ++root.left_count;\r\n      if (root.left == null) {\r\n        root.left = new Node(val);            \r\n        return 0;\r\n      } \r\n      return insert(root.left, val);\r\n    } else  {\r\n      if (root.right == null) {\r\n        root.right = new Node(val);\r\n        return root.less_or_equal();\r\n      }\r\n      return root.less_or_equal() + insert(root.right, val);\r\n    }\r\n  }\r\n}<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u4e00\u4e2a\u6570\u7ec4\uff0c\u5bf9\u4e8e\u6570\u7ec4\u4e2d\u7684\u6bcf\u4e2a\u5143\u7d20\uff0c\u8fd4\u56de\u4e00\u5171\u6709\u591a\u5c11\u5728\u5b83\u4e4b\u540e\u7684\u5143\u7d20\u6bd4\u5b83\u5c0f\u3002 Problem: You are given an integer array\u00a0nums\u00a0and you have to return a new\u00a0counts\u00a0array. The\u00a0counts\u00a0array has the property where\u00a0counts[i]\u00a0is the number of smaller elements to&#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],"tags":[202,74,204,217,203],"class_list":["post-1487","post","type-post","status-publish","format-standard","hentry","category-array","tag-binary-indexed-tree","tag-bst","tag-fenwick-tree","tag-hard","tag-reversed-pairs","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1487","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=1487"}],"version-history":[{"count":14,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1487\/revisions"}],"predecessor-version":[{"id":3795,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1487\/revisions\/3795"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=1487"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=1487"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=1487"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}