leetcode315. 计算右侧小于当前元素的个数（Python3）_leetcode 315 python

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

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

示例:

输入: [5,2,6,1]
输出: [2,1,1,0] 
解释:
5 的右侧有 2 个更小的元素 (2 和 1).
2 的右侧仅有 1 个更小的元素 (1).
6 的右侧有 1 个更小的元素 (1).
1 的右侧有 0 个更小的元素.
1
2
3
4
5
6
7

---

方法：归并排序

思路：

本题类似于面试题51.数组中的逆序对。使用归并排序的方法。

归并排序就是逐渐的将两个排序好的子数组进行合并，最后将整个数组排序。我们的排序进行降序排序。比如示例[5,2,6,1]，首先分成两个[5,2]和[6,1]，这两个子数组都可以继续分，分为[5]、[2]和[6]、[1]，不可继续分了，结束递归，开始向上合并，[5]、[2]合并为[5,2]，[6]、[1]排序为[6,1]；继续合并为[6,5,2,1]，结束排序。

那么，归并排序这个过程，和我们右侧小于当前元素个数有什么关系呢，我们以合并[5,2]和[6,1]的时候为例。

因为我们进行排序之后，nums中的位置都改变了，而我们最后需要返回的是nums的原来位置对应的右侧小于该元素的数量。因此我们定义一个数组numsarr，每个元素为[nums[i],i]，即保存nums每个元素的值和其原来的坐标。维护res数组，res[i]保存nums[i]的右侧小于该元素个数。

在归并排序过程中，我们需要更新某个点对应的右侧小于该元素数量时，设该点为t