{"id":157,"date":"2015-12-13T13:14:31","date_gmt":"2015-12-13T13:14:31","guid":{"rendered":"http:\/\/emacslisp.com\/?p=157"},"modified":"2015-12-13T13:17:01","modified_gmt":"2015-12-13T13:17:01","slug":"leetcode-count-of-smaller-numbers-after-self","status":"publish","type":"post","link":"http:\/\/emacslisp.com\/?p=157","title":{"rendered":"Leetcode &#8211; Count of Smaller Numbers After Self"},"content":{"rendered":"<p>Here is leetcode&#8217;s new hard level question:<br \/>\nhttps:\/\/leetcode.com\/problems\/count-of-smaller-numbers-after-self\/<\/p>\n<p>The basic idea is using two for to loop though to counter smaller number on its left.<br \/>\nSolution1:<\/p>\n<pre lang=\"java\" line=\"1\">\r\npublic List<Integer> countSmaller(int[] nums) {\r\nList<Integer> result = new ArrayList<>();\r\n        \r\nresult.add(0);\r\n        \r\nfor(int i = nums.length - 2;i>=0;i--)\r\n{\r\n    int target = nums[i];\r\n    int count = 0;\r\n    for(int j=i+1;j<=nums.length-1;j++)\r\n    {\r\n        if(nums[j]<=target)\r\n            count++;\r\n    }\r\n    result.add(count);\r\n}\r\n        \r\nCollections.reverse(result);\r\n        \r\nreturn result;\r\n}\r\n<\/pre>\n<p>Solution 2:<\/p>\n<p>Solution 1 is using two loops to go though to compare.<\/p>\n<p>This solution is faster the second loop using tree.<\/p>\n<pre lang=\"java\" line=\"1\"> \r\n\r\npackage leetcodetest;\r\n\r\nimport java.util.ArrayList;\r\nimport java.util.Collections;\r\nimport java.util.List;\r\n\r\n\/**\r\n *\r\n * @author wudi\r\n *\/\r\npublic class CountSmaller2 {\r\n    \r\n    public class xTreenode\r\n    {\r\n        public xTreenode left = null;\r\n        public xTreenode right = null;\r\n        int count = 1;\r\n        \r\n        int val;\r\n        \r\n        public xTreenode(int x)\r\n        {\r\n            val = x;\r\n        }\r\n        \r\n    }\r\n    \r\n    public int add(xTreenode root,int x)\r\n    {\r\n        int count = 0;\r\n        \r\n        while(true)\r\n        {\r\n            if(x <= root.val)\r\n            {\r\n                root.count++;\r\n\r\n                if(root.left == null){\r\n                    root.left = new xTreenode(x);\r\n                    break;\r\n                }\r\n\r\n                root = root.left;\r\n            }\r\n            else\r\n            {\r\n                count += root.count;\r\n                if(root.right == null)\r\n                {\r\n                    root.right = new xTreenode(x);\r\n                    break;\r\n                }\r\n                root = root.right;\r\n            }\r\n        }\r\n        \r\n        return count;\r\n    }\r\n    \r\n    public List<Integer> countSmaller(int[] nums) {\r\n        List<Integer> result = new ArrayList<>();\r\n        if(nums == null || nums.length == 0) \r\n            return result;\r\n        xTreenode root = new xTreenode(nums[nums.length - 1]);\r\n        result.add(0);\r\n        \r\n        for(int i=nums.length - 2;i>=0;i--)\r\n        {\r\n            int count = add(root,nums[i]);\r\n            result.add(count);\r\n        }\r\n        \r\n        Collections.reverse(result);\r\n        \r\n        return result;\r\n    }\r\n     public static void main(String[] args) {\r\n         int[] nums = {2,0,1};\r\n        \r\n        CountSmaller2 c = new CountSmaller2();\r\n        System.out.println(c.countSmaller(nums));\r\n     }\r\n}\r\n\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Here is leetcode&#8217;s new hard level question: https:\/\/leetcode.com\/problems\/count-of-smaller-numbers-after-self\/ The basic idea is using two for to loop though to counter smaller number on its left. Solution1: public List countSmaller(int[] nums) { List result = new ArrayList(); result.add(0); for(int i = nums.length &#8211; 2;i>=0;i&#8211;) { int target = nums[i]; int count = 0; for(int j=i+1;j<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7],"tags":[],"class_list":["post-157","post","type-post","status-publish","format-standard","hentry","category-algorithm"],"_links":{"self":[{"href":"http:\/\/emacslisp.com\/index.php?rest_route=\/wp\/v2\/posts\/157","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/emacslisp.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/emacslisp.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/emacslisp.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/emacslisp.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=157"}],"version-history":[{"count":4,"href":"http:\/\/emacslisp.com\/index.php?rest_route=\/wp\/v2\/posts\/157\/revisions"}],"predecessor-version":[{"id":161,"href":"http:\/\/emacslisp.com\/index.php?rest_route=\/wp\/v2\/posts\/157\/revisions\/161"}],"wp:attachment":[{"href":"http:\/\/emacslisp.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=157"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/emacslisp.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=157"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/emacslisp.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=157"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}