0%

### leetcode Count of Smaller Numbers After Self

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Given nums = [5, 2, 6, 1]

To the right of 5 there are 2 smaller elements (2 and 1). To the right of 2 there is only 1 smaller element (1). To the right of 6 there is 1 smaller element (1). To the right of 1 there is 0 smaller element.

Return the array [2, 1, 1, 0].

1. 使用逆序数有经典的解法为合并排序。

2. 用Fenwick树  关于Fenwick 树介绍 Binary indexed tree (Fenwick tree)

• 简单说就是看当前数在nums中排第几，然后对小于它的数求个数和
• 具体的做法是先离散化，确定每个数载nums中排到第几 （去重和排序）
• 然后从右向左扫描，每次统计比其小于1的个数（就是求和），然后把当前的数加入Fenwick中。

C++

C++

Python