315.count-of-smaller-numbers-after-self.md

给定一个整数数组 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

插入排序 + 二分

从右侧第一个元素开始插入排序，二分法查找插入位置，位置即为右边小于该元素的元素数

var countSmaller = function (nums) {
  let sorted = [],
    ans = [];
  for (let i = nums.length - 1; i >= 0; i--) {
    let index = find(sorted, nums[i]);
    sorted.splice(index, 0, nums[i]);
    ans[i] = index;
  }
  return ans;
};
function find(nums, n) {
  if (nums.length == 0) return 0;
  let l = 0,
    r = nums.length;
  while (l < r) {
    let mid = (l + r) >> 1;
    if (nums[mid] >= n) r = mid;
    else l = mid + 1;
  }
  return l;
}