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

315. 计算右侧小于当前元素的个数思路是构建二叉搜索树，因为二叉搜索树（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；（3）左、右子树也分别为二叉排序树；（4）没有键值相等的结点。通过这个规律可以得出当前root左边的节点全部小于当前root的val值

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var countSmaller = function (nums) {
  const len = nums.length;
  let count = new Array(len).fill(0);
  if (len < 2) {
    return count;
  }
  let bst = new Node(nums[len - 1]);
  for (let i = len - 2; i >= 0; i--) {
    count[i] = insert(bst, nums[i]);
  }
  return count;
}

/**
 * @param {object} root
 * @param {number} val
 * @return {number}
 */
var insert = function (root, val) {
  const curNode = new Node(val);
  var smaller = 0;
  while (root) {
    if (val < root.val) { // go left
      root.count++; // 当前节点的val大于val 则其count加1
      if (root.left === null) {
        root.left = curNode;
        return smaller;
      } else {
        root = root.left
      }
    } else if (val > root.val) { // go to right
      smaller += root.count + 1; // 当前节点的val小于val 则其smaller等于当前节点count + 1的值
      if (root.right === null) {
        root.right = curNode;
        return smaller;
      } else {
        root = root.right;
      }
    } else {
      // 重复值时 也算作当前节点的val > val count+1 , 通过dup + 1，标记重复 然后想减去抵消++结果
      return smaller + (root.count++) - (root.dup++);
    }
  }
}

var Node = function (val) {
  this.val = val;
  this.left = null;
  this.right = null;
  this.count = 0;
  this.dup = 0;
}

tailgo / poorguy-fly

315. 计算右侧小于当前元素的个数 #20