0315. Count of Smaller Numbers After Self¶
题目信息¶
- 题号:
0315
- 难度:
Hard
- 主题:
数组、右侧元素、严格比较、按原下标返回
- 原题:
- 重点:
只统计当前位置右侧的元素、必须严格小于、结果位置与原数组一一对应
题目重述¶
给定整数数组 nums,构造同样长度的数组 counts。对每个下标 i,counts[i] 等于所有满足 j > i 且 nums[j] < nums[i] 的下标 j 的数量。
比较必须是严格小于,因此与当前值相等的右侧元素不计入。nums 的长度位于 [1, 10^5],每个元素位于 [-10^4, 10^4]。返回结果必须保持原下标顺序,最后一个位置右侧没有元素,所以其统计值一定为 0。
自建示例¶
包含重复值:
输入:nums = [4, 1, 3, 1]
输出:[3, 0, 1, 0]
解释:4 的右侧三个值都比它小;第一个 1 右侧没有严格更小值;3 的右侧只有最后一个 1 更小。
相等值不算更小:
输入:nums = [2, 2]
输出:[0, 0]
解释:右侧的 2 与当前值相等,不满足严格小于。
从右向左,把右侧变成已处理集合¶
如果从左向右处理 nums[i],右侧元素还没有进入数据结构;从右向左扫描则相反:处理下标 i 时,树状数组中恰好保存了所有下标大于 i 的元素。问题就变成统计已加入集合中有多少值严格小于 nums[i],统计完成后再把当前值加入,供更左侧位置使用。
树状数组需要有序的离散下标,因此先复制数组、排序并去重,把每个原值映射为从 1 开始的排名。值小于当前值对应的正是 rank - 1 及以前的排名;查询这个前缀而不是查询 rank,会自动排除相等值,保持题目要求的严格比较。
C++ 实现¶
class Solution {
std::vector<int> tree;
void add(int index) {
for (int i = index; i < static_cast<int>(tree.size());
i += i & -i) {
++tree[i];
}
}
int query(int index) const {
int result = 0;
for (int i = index; i > 0; i -= i & -i) {
result += tree[i];
}
return result;
}
public:
std::vector<int> countSmaller(std::vector<int>& nums) {
std::vector<int> values = nums;
std::sort(values.begin(), values.end());
values.erase(std::unique(values.begin(), values.end()),
values.end());
tree.assign(values.size() + 1, 0);
std::vector<int> result(nums.size(), 0);
for (int i = static_cast<int>(nums.size()) - 1; i >= 0; --i) {
int rank = static_cast<int>(
std::lower_bound(values.begin(), values.end(), nums[i])
- values.begin()) + 1;
result[i] = query(rank - 1);
add(rank);
}
return result;
}
};
代码分析¶
扫描方向保证树状数组的元素来源就是“当前位置右侧”,结果数组按原下标直接写回,不需要在最后重新排列。离散化只改变比较顺序,不改变小于、等于的关系;查询 rank - 1 是排除重复值的关键。排序离散化需要 O(n log n),之后每个位置一次查询和一次更新,时间仍为 O(n log n),额外空间为 O(n)。