难度困难
给你一个整数数组 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
标签：pairs,nums,self,个数,mid,315,aux,右侧 From： https://www.cnblogs.com/zle1992/p/17475330.html