力扣第 315 题
题目
给你一个整数数组 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
分析
#1
考虑从右往左遍历，维护右侧元素的有序集合，二分查找即可。
1
2
3
4
5
6
7
8
9
|
class Solution:
def countSmaller(self, nums: List[int]) -> List[int]:
from sortedcontainers import SortedList
res = []
sl = SortedList()
for x in nums[::-1]:
res.append(sl.bisect_left(x))
sl.add(x)
return res[::-1]
|
727 ms
#2
也可以用树状数组维护，注意先离散化处理负数。
解答
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
|
class BIT:
def __init__(self,n):
self.n = n+1
self.t = [0]*(n+1)
def update(self,i,x):
i += 1
while i<self.n:
self.t[i]+=x
i += i&-i
def get(self,i):
res,i = 0,i+1
while i:
res += self.t[i]
i &= i-1
return res
class Solution:
def countSmaller(self, nums: List[int]) -> List[int]:
d = {x:i for i,x in enumerate(sorted(set(nums)))}
A = [d[x] for x in nums[::-1]]
res = []
tree = BIT(max(A)+1)
for x in A:
res.append(tree.get(x-1))
tree.update(x,1)
return res[::-1]
|
607 ms
*附加
- 还可以类似归并排序，采用cdq分治法
- 先递归地将前后两部分排序
- 然后归并两部分，并计算后半部分对前半部分的贡献
- 于是在递归过程中，计算出了所有后面元素对前面元素的贡献
- 提前将下标排序，dfs 只需计算贡献，就可以随意改变子问题递归的顺序，能解决更多问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution:
def countSmaller(self, nums: List[int]) -> List[int]:
def cdq(A,l,r):
if l==r:
return
m = (l+r)//2
B,C = [],[]
for i in A:
if i>m:
C.append(i)
else:
B.append(i)
res[i]+=len(C)
cdq(B,l,m)
cdq(C,m+1,r)
n = len(nums)
res = [0]*n
A = sorted(range(n),key=lambda i:nums[i])
cdq(A,0,n-1)
return res
|
695 ms