给定一个长度为 n 的数组 nums ,请你返回一个新数组 count ,其中 count[i] 是 nums[i] 右侧小于 nums[i] 的元素个数。
数据范围: ,数组元素值满足
import java.util.*; public class Solution { public ArrayList<Integer> smallerCount1(ArrayList<Integer> nums) { // 最大最小取平均数 int min = nums.get(0); int max = nums.get(0); for (int num : nums) { if (num < min) { min = num; } else if (num > max) { max = num; } } int mid = (min + max) >> 1; // 设置根节点 TreeNode head = new TreeNode(mid); head.count = 0; for (int i = nums.size() - 1; i >= 0; i--) { // 从右向左遍历 int num = nums.get(i); TreeNode par = head; // 每次从根节点出发 int count = 0; // 计算小于当前数num的值 while (true) { if (num == par.val) { // 当值相等,说明找到了,该节点计数+1 par.count = par.count + 1; // count值加上当前节点的leftCount,leftCount每次添加节点的时候左滑计数,如果当前节点是父节点右孩子,代表: 父节点值 < num < 当前节点值 count = count + par.leftCount; break; } else if (num > par.val) { // 向右滑 count = count + par.leftCount + par.count; // 右滑结算当前节点的leftCount与当前节点的数量 TreeNode right = par.right; if (right == null) { // 右孩子为空说明到头了,初始化右孩子并且设置为count=1(构造设置) right = new TreeNode(num); par.right = right; break; } // 右孩子不为空,右滑继续 par = right; } else { // 小于当前节点值,左滑并且leftCount+1 par.leftCount = par.leftCount + 1; TreeNode left = par.left; if (left == null) { // 如果没左孩子,初始化左孩子,退出循环 left = new TreeNode(num); par.left = left; break; } // 左孩子不为空,继续循环向下 par = left; } } // 设置结果 nums.set(i, count); } return nums; } private static class TreeNode { private int val; private int leftCount; private int count; private TreeNode left; private TreeNode right; public TreeNode(int val) { this.val = val; count = 1; } } }