<div>
You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].
Example 1:
<pre>Input: nums = [5,2,6,1] Output: [2,1,1,0] Explanation: To the right of 5 there are 2 smaller elements (2 and 1). To the right of 2 there is only 1 smaller element (1). To the right of 6 there is 1 smaller element (1). To the right of 1 there is 0 smaller element. </pre>
Example 2:
<pre>Input: nums = [-1] Output: [0] </pre>
Example 3:
<pre>Input: nums = [-1,-1] Output: [0,0] </pre>
Constraints:
1 <= nums.length <= 10<sup>5</sup>-10<sup>4</sup> <= nums[i] <= 10<sup>4</sup>
</div>
题目大意：
数组中，统计每一位比自己小的数。
解题思路：
一开始考虑用递减栈。但不可行, 因为这是统计题，而不是求比自己大的一个数LeetCode 503 Next Greater Element II。类似于merge sort，考虑统计逆序数
解题步骤：
N/A
注意事项：
- 由于mergesort会改变数组顺序，所以统计数组count也要对应的数也会变，所以将原数组变成(数值, 下标)对，count就可以统计原数组
- 计算逆序对时候，放在nums[i][0] <= nums[j][0]中，核心在count[nums[i][1]] += j - mid - 1
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33def countSmaller(self, nums: List[int]) -> List[int]:
count = [0] * len(nums)
num_with_idx = [(n, i) for i, n in enumerate(nums)]
self.merge_sort(num_with_idx, 0, len(nums) - 1, count)
return count
def merge_sort(self, nums, start, end, count):
if start >= end:
return
mid = start + (end - start) // 2
self.merge_sort(nums, start, mid, count)
self.merge_sort(nums, mid + 1, end, count)
self.merge(nums, start, mid, end, count)
def merge(self, nums, start, mid, end, count):
i, j = start, mid + 1
res = []
while i <= mid and j <= end:
if nums[i][0] <= nums[j][0]:
res.append(nums[i])
count[nums[i][1]] += j - mid - 1
i += 1
else:
res.append(nums[j])
j += 1
while i <= mid:
res.append(nums[i])
count[nums[i][1]] += j - mid - 1
i += 1
while j <= end:
res.append(nums[j])
j += 1
nums[start:end + 1] = res
算法分析：
时间复杂度为O(nlogn)，空间复杂度O(n)
