目录

0315:计算右侧小于当前元素的个数(★★)

力扣第 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