LeetCode 题解工作台
计算右侧小于当前元素的个数
给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。 示例 1： 输入： nums = [5,2,6,1] 输出： [2,1,1,0] 解释： 5 的右侧有 2 个更小…
7
题型
4
代码语言
3
相关题
当前训练重点
困难 · 二分·搜索·答案·空间
答案摘要
树状数组，也称作“二叉索引树”（Binary Indexed Tree）或 Fenwick 树。 它可以高效地实现如下两个操作： 1. 单点更新 `update(x, delta)`： 把序列 x 位置的数加上一个值 delta；
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
给你一个整数数组 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
解题思路
方法一：树状数组
树状数组，也称作“二叉索引树”（Binary Indexed Tree）或 Fenwick 树。 它可以高效地实现如下两个操作：
- 单点更新
update(x, delta)： 把序列 x 位置的数加上一个值 delta； - 前缀和查询
query(x)：查询序列[1,...x]区间的区间和，即位置 x 的前缀和。
这两个操作的时间复杂度均为 。
树状数组最基本的功能就是求比某点 x 小的点的个数（这里的比较是抽象的概念，可以是数的大小、坐标的大小、质量的大小等等）。
比如给定数组 a[5] = {2, 5, 3, 4, 1}，求 b[i] = 位置 i 左边小于等于 a[i] 的数的个数。对于此例，b[5] = {0, 1, 1, 2, 0}。
解决方案是直接遍历数组，每个位置先求出 query(a[i])，然后再修改树状数组 update(a[i], 1) 即可。当数的范围比较大时，需要进行离散化，即先进行去重并排序，然后对每个数字进行编号。
class BinaryIndexedTree:
def __init__(self, n):
self.n = n
self.c = [0] * (n + 1)
@staticmethod
def lowbit(x):
return x & -x
def update(self, x, delta):
while x <= self.n:
self.c[x] += delta
x += BinaryIndexedTree.lowbit(x)
def query(self, x):
s = 0
while x > 0:
s += self.c[x]
x -= BinaryIndexedTree.lowbit(x)
return s
class Solution:
def countSmaller(self, nums: List[int]) -> List[int]:
alls = sorted(set(nums))
m = {v: i for i, v in enumerate(alls, 1)}
tree = BinaryIndexedTree(len(m))
ans = []
for v in nums[::-1]:
x = m[v]
tree.update(x, 1)
ans.append(tree.query(x - 1))
return ans[::-1]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate demonstrates understanding of binary search in the context of array manipulation.
- question_mark
The candidate can efficiently combine Divide and Conquer strategies with advanced data structures like BIT or Segment Tree.
- question_mark
The candidate effectively chooses an optimal approach based on problem constraints.
常见陷阱
外企场景- error
Failing to recognize that a brute-force solution is too slow for large inputs.
- error
Misunderstanding the need for sorting or binary search when counting smaller elements.
- error
Incorrectly implementing the tree or merge phase, resulting in inaccurate counts.
进阶变体
外企场景- arrow_right_alt
Using Merge Sort with a slight variation to track the counts of smaller numbers while merging.
- arrow_right_alt
Employing Binary Indexed Tree (BIT) for an optimized solution, considering different update/query strategies.
- arrow_right_alt
Using Segment Tree for efficient range queries and handling larger arrays more efficiently.