计算右侧小于当前元素的个数

给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。

示例:

输入: [5,2,6,1]

输出: [2,1,1,0]

解释:

5 的右侧有 2 个更小的元素 (2 和 1).

2 的右侧仅有 1 个更小的元素 (1).

6 的右侧有 1 个更小的元素 (1).

1 的右侧有 0 个更小的元素.

使用BST进行统计。时间复杂度O(nlogn)。

 import java.util.ArrayList;

 import java.util.List;

 public class Solution {

     TreeNode root;

     private int smaller(TreeNode current, int val) {

         current.size ++;

         if (current.val < val) {

             if (current.right == null) current.right = new TreeNode(val);

             return current.size - 1 - current.right.size + smaller(current.right, val);

         } else if (current.val > val) {

             if (current.left == null) current.left = new TreeNode(val);

             return smaller(current.left, val);

         } else {

             return current.left == null? 0 : current.left.size;

         }

     }

     public List<Integer> countSmaller(int[] nums) {

         List<Integer> result = new ArrayList<>(nums.length);

         int[] smaller = new int[nums.length];

         if (nums == null || nums.length == 0) return result;

         root = new TreeNode(nums[nums.length-1]);

         for(int i=nums.length-1; i>=0; i--) {

             smaller[i] = smaller(root, nums[i]);

         }

         for(int i=0; i<smaller.length; i++) result.add(smaller[i]);

         return result;

     }

 }

 class TreeNode {

     int val;

     int size;

     TreeNode left, right;

     TreeNode(int val) {

         this.val = val;

     }

 }

Leetcode 315.计算右侧小于当前元素的个数的相关教程结束。