315.计算右侧小于当前元素的个数
解题思路
1、 暴力算法，两层for循环嵌套， O(n^2) 最后测试会超时，需要优化。
2、 方法1：使用 BST(二叉搜索/排序数)
BST(二叉搜索/排序数) Java代码
class Solution {
// 采用二叉搜索的做法，在树节点除了有val值外，还有个count值，用于记录它的左子树上有多少个节点
// 这样，最开始那个点形成的树节点，count值是0
public List<Integer> countSmaller(int[] nums) {
List<Integer> list = new ArrayList<>();
if (nums == null || nums.length <= 0) return list; int[] ret = new int[nums.length]; TreeNode root = null; for (int i = nums.length - 1; i >= 0; i--) { root = insert(root, new TreeNode(nums[i]), ret, i); } for (int n : ret) { list.add(n); } return list; } /** * 插入到树里面的时候，还需要更小count域的值。 * @param root 根节点 * @param node 待插入的节点 * @param ret 当node插入到树之后，实际上它的ret已经是确定的来 * @param i 数组下标 */ public TreeNode insert(TreeNode root, TreeNode node, int[] ret, int i) { if (root == null) { root = node; return root; } // 如果待插入的数比较小，或者相等的时候，就往左子数中插入，且根节点的count加1 if(node.val <= root.val) { root.count++; root.left = insert(root.left, node, ret, i); } else { // 对应点的count增加越过的那个节点的count值 + 1。因为越过的那个节点也比它小 ret[i] += root.count + 1; root.right = insert(root.right, node, ret, i); } return root; } // 树节点中除了val，还有个count，来统计它的左子树的节点 class TreeNode { int val; int count; TreeNode left; TreeNode right; public TreeNode(int value) { this.val = value; this.count = 0; this.left = null; this.right = null; } } }
部分图片来源于网络，版权归原作者，侵删。