49. 计算右侧小于当前元素的个数
题目链接
题目描述
给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 中每个位置 i 的值表示在 nums[i] 右侧且比它小的元素个数。
题目示例
输入：[5, 2, 6, 1]
输出：[2, 1, 1, 0]
解释：
- 5 的右边有 2 个比它小的数 (2, 1)
- 2 的右边有 1 个比它小的数 (1)
- 6 的右边有 1 个比它小的数 (1)
- 1 的右边没有比它小的数
算法思路
这道题的核心思路其实和求逆序对非常相似。不同之处在于，我们不需要统计总的逆序对数量，而是要为每个元素单独记录其右侧有多少个更小的值。
归并排序本身会改变元素的位置，这会导致我们无法直接通过下标找到原始位置。因此，我们需要引入一个辅助数组来绑定元素值和它的原始下标。在归并过程中，每当发现左半部分的元素大于右半部分的元素时，就可以确定右半部分剩余的所有元素都比当前左半部分元素小，从而累加计数。
C++ 算法代码
class Solution {
public:
vector<int> counts;
vector<int> index; // 记录 nums 中当前元素的原始下标
vector<int> tmp;
vector<int> tmpi; // 临时记录合并后对应元素位置变化下标随之变化的数组
vector<int> countSmaller(vector<int>& nums) {
counts.resize(nums.size());
index.resize(nums.size());
tmp.resize(nums.size());
tmpi.(nums.());
( i = ; i < nums.(); i++) {
index[i] = i;
}
(nums, , nums.() - );
counts;
}
{
(left == right) {
;
}
mid = (right - left) / + left;
(nums, left, mid);
(nums, mid + , right);
cur1 = left, cur2 = mid + , i = ;
(cur1 <= mid && cur2 <= right) {
(nums[cur1] > nums[cur2]) {
counts[index[cur1]] += right - cur2 + ;
tmpi[i] = index[cur1];
tmp[i++] = nums[cur1++];
} {
tmpi[i] = index[cur2];
tmp[i++] = nums[cur2++];
}
}
(cur1 <= mid) {
tmpi[i] = index[cur1];
tmp[i++] = nums[cur1++];
}
(cur2 <= right) {
tmpi[i] = index[cur2];
tmp[i++] = nums[cur2++];
}
( j = left; j <= right; j++) {
nums[j] = tmp[j - left];
index[j] = tmpi[j - left];
}
}
};
