🧺 Space complexity: O(n), to store the sorted_list.

Method 5 - Segment tree

Here is the approach:

Handling Negative Numbers: Normalize the array by offsetting negative values.
Segment Tree Operations: Implement the segment tree with operations to add elements, delete elements, and query counts within a range.

Code

[{"language":"Java","code":"public class Solution {\n\tstatic class segmentTreeNode {\n\t\tint start, end, count;\n\t\tsegmentTreeNode left, right;\n\t\tsegmentTreeNode(int start, int end, int count) {\n\t\t\tthis.start = start;\n\t\t\tthis.end = end;\n\t\t\tthis.count = count;\n\t\t\tleft = null;\n\t\t\tright = null;\n\t\t}\n\t}\n\tpublic static List<Integer> countSmaller(int[] nums) {\n\t\t// write your code here\n\t\tList<Integer> result = new ArrayList<Integer>();\n\n\t\tint min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;\n\t\tfor (int i : nums) {\n\t\t\tmin = Math.min(min, i);\n\n\t\t}\n\t\tif (min < 0) {\n\t\t\tfor (int i = 0; i < nums.length; i++) {\n\t\t\t\tnums[i] -= min;//deal with negative numbers, seems a dummy way\n\t\t\t}\n\t\t}\n\t\tfor (int i : nums) {\n\t\t\tmax = Math.max(max, i);\n\t\t}\n\t\tsegmentTreeNode root = build(0, max);\n\t\tfor (int i = 0; i < nums.length; i++) {\n\t\t\tupdateAdd(root, nums[i]);\n\t\t}\n\t\tfor (int i = 0; i < nums.length; i++) {\n\t\t\tupdateDel(root, nums[i]);\n\t\t\tresult.add(query(root, 0, nums[i] - 1));\n\t\t}\n\t\treturn result;\n\t}\n\tpublic static segmentTreeNode build(int start, int end) {\n\t\tif (start > end) return null;\n\t\tif (start == end) return new segmentTreeNode(start, end, 0);\n\t\tint mid = (start + end) / 2;\n\t\tsegmentTreeNode root = new segmentTreeNode(start, end, 0);\n\t\troot.left = build(start, mid);\n\t\troot.right = build(mid + 1, end);\n\t\troot.count = root.left.count + root.right.count;\n\t\treturn root;\n\t}\n\n\tpublic static int query(segmentTreeNode root, int start, int end) {\n\t\tif (root == null) return 0;\n\t\tif (root.start == start && root.end == end) return root.count;\n\t\tint mid = (root.start + root.end) / 2;\n\t\tif (end < mid) {\n\t\t\treturn query(root.left, start, end);\n\t\t} else if (start > end) {\n\t\t\treturn query(root.right, start, end);\n\t\t} else {\n\t\t\treturn query(root.left, start, mid) + query(root.right, mid + 1, end);\n\t\t}\n\t}\n\n\tpublic static void updateAdd(segmentTreeNode root, int val) {\n\t\tif (root == null || root.start > val || root.end < val) return;\n\t\tif (root.start == val && root.end == val) {\n\t\t\troot.count ++;\n\t\t\treturn;\n\t\t}\n\t\tint mid = (root.start + root.end) / 2;\n\t\tif (val <= mid) {\n\t\t\tupdateAdd(root.left, val);\n\t\t} else {\n\t\t\tupdateAdd(root.right, val);\n\t\t}\n\t\troot.count = root.left.count + root.right.count;\n\t}\n\n\tpublic static void updateDel(segmentTreeNode root, int val) {\n\t\tif (root == null || root.start > val || root.end < val) return;\n\t\tif (root.start == val && root.end == val) {\n\t\t\troot.count --;\n\t\t\treturn;\n\t\t}\n\t\tint mid = (root.start + root.end) / 2;\n\t\tif (val <= mid) {\n\t\t\tupdateDel(root.left, val);\n\t\t} else {\n\t\t\tupdateDel(root.right, val);\n\t\t}\n\t\troot.count = root.left.count + root.right.count;\n\t}\n}","lang":"java","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e

Related Tags