315. 计算右侧小于当前元素的个数-526互联

难度困难

给你一个整数数组 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 <= 105
-104 <= nums[i] <= 104

#
# @lc app=leetcode.cn id=315 lang=python3
#
# [315] 计算右侧小于当前元素的个数
#

# @lc code=start
from collections import defaultdict

class Solution:
    def __init__(self) -> None:
        self.res = []
    def countSmaller(self, nums: List[int]) -> List[int]:
        def merge(nums,aux,l,mid,r):
            i = l 
            j = mid 
            k = l
            while i < mid and j < r:
                if aux[i][0] <= aux[j][0]:
                    nums[k] = aux[i]
                    self.res[nums[k][1]] += j - mid
                    i+=1
                    k+=1
                else:
                    nums[k] = aux[j]
                    j+=1
                    k+=1

            while i < mid:
                nums[k] = aux[i]
                self.res[nums[k][1]] += j - mid
                i+=1
                k+=1
            while j < r:
                nums[k] = aux[j]
                j+=1
                k+=1
            aux[l:r] = nums[l:r] 

        def merge_and_sort(nums,aux,l,r):
            #print(l,r)
            if l >= r-1:
                return 
            mid = l + (r-l)//2
            merge_and_sort(nums,aux,l,mid)
            merge_and_sort(nums,aux,mid,r)
            merge(nums,aux,l,mid,r)



        self.res = [0] * len(nums)
        num_pairs = []
        for i in range(len(nums)):
            num_pairs.append((nums[i],i))
        aux = num_pairs.copy()
        merge_and_sort(num_pairs,aux,0,len(nums))    
        print(num_pairs)
        return self.res 
# @lc code=end