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

Link

力扣

Problem

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

示例 1：

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

示例2：

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

示例3:

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

提示：

• 1 <= nums.length <= 10^5

• -104 <= nums[i] <= 10^4

Solution

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)
}

C++