目录

315. 计算右侧小于当前元素的个数

解析代码

---

力扣315. 计算右侧小于当前元素的个数

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 <= 10^5
• -10^4 <= nums[i] <= 10^4

class Solution {
public:
	vector<int> countSmaller(vector<int>& nums) {

};

---

解析代码

class Solution {
	vector<int> ret;
	vector<int> index; // nums中元素的原始下标
	vector<int> tmp_nums;
	vector<int> tmp_index; // 和nums里的元素绑定一起移动
public:
	vector<int> countSmaller(vector<int>& nums) {
		int n = nums.size();
		ret.resize(n);
		index.resize(n);
		tmp_nums.resize(n);
		tmp_index.resize(n);
		for (int i = 0; i < n; ++i)
		{
            index[i] = i;
        }
		mergeSortCnt(nums, 0, n - 1);
		return ret;
	}

	void mergeSortCnt(vector<int>& nums, int left, int right)
	{
		if (left >= right)
			return;
		int mid = (left + right) >> 1;
		mergeSortCnt(nums, left, mid);
		mergeSortCnt(nums, mid + 1, right);

		int cur1 = left, cur2 = mid + 1, i = 0;
		while (cur1 <= mid && cur2 <= right)
		{
			if (nums[cur1] > nums[cur2])
			{
				ret[index[cur1]] += (right - cur2 + 1);
				tmp_nums[i] = nums[cur1];
				tmp_index[i++] = index[cur1++];
			}
			else
			{
				tmp_nums[i] = nums[cur2];
				tmp_index[i++] = index[cur2++];
			}
		}
		while (cur1 <= mid)
		{
			tmp_nums[i] = nums[cur1];
			tmp_index[i++] = index[cur1++];
		}
		while (cur2 <= right)
		{
			tmp_nums[i] = nums[cur2];
			tmp_index[i++] = index[cur2++];
		}
		for (int j = left; j <= right; ++j)
		{
			nums[j] = tmp_nums[j - left];
			index[j] = tmp_index[j - left];
		}
	}
};