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

## Link

{% embed url="<https://leetcode.cn/problems/count-of-smaller-numbers-after-self/>" %}

## Problem

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

示例 1：

{% code overflow="wrap" %}

```
输入：nums = [5,2,6,1]
输出：[2,1,1,0] 
解释：
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素
```

{% endcode %}

示例2：

{% code overflow="wrap" %}

```
输入：nums = [-1]
输出：[0]
```

{% endcode %}

示例3:

{% code overflow="wrap" %}

```
输入：nums = [-1,-1]
输出：[0,0]
```

{% endcode %}

提示：

* `1 <= nums.length <= 10^5`
* `-104 <= nums[i] <= 10^4`

## Solution

{% tabs %}
{% tab title="Go" %}

```go
var (
    index []int 
    cnt []int
)

func countSmaller(nums []int) []int {
    n := len(nums)
    index = make([]int, n)
    cnt = make([]int, n)

    for i := range index {
        index[i] = i
    }

    mergesort(nums, 0, len(nums)-1)
    return cnt
}

func mergesort(nums []int, l, r int) {
    if l >= r {
        return 
    }
    m := l + (r - l) >> 1 
    mergesort(nums, l, m)
    mergesort(nums, m+1, r)

    if nums[index[m]] <= nums[index[m+1]] {
        return 
    }

    i, j := l, m + 1
    helper := make([]int, r-l+1)
    for k := range helper {
        if j > r || (i <= m && nums[index[i]] <= nums[index[j]]) {
            cnt[index[i]] += j - m - 1
            helper[k] = index[i]; i++ 
        } else {
            helper[k] = index[j]; j++
        }
    }
    copy(index[l:r+1], helper)
}
```

{% endtab %}

{% tab title="C++" %}

```cpp
```

{% endtab %}
{% endtabs %}