315 Count of Smaller Numbers After Self

题目

315 Count of Smaller Numbers After Self

题解

题目要求：给定一个数组，对于每个元素，求出在其之后的元素中比它小的个数。

这题暴力求解的话非常简单，对每个元素直接遍历其后面的所有元素就行了，但是时间复杂度为\(O(n^2)\)。

为了进行算法优化，我们需要充分利用能够得到的各种信息。 一个简单的做法是开辟一个访问标记数组，从小到大访问每个元素，对每个元素，统计在它后面已被访问过（也就是比它小）的元素的个数。这样做虽然利用了元素被访问的信息，但是效率太低。

为了提高效率，我们需要能够快速统计出某一位置后面已访问的元素个数的方法。为了更好地理解并解决问题，我们需要为问题选择一个恰当的表示形式。因为统计的时候只累加已访问的元素，所以不妨把已访问的元素看成是值为1的元素，把未访问的元素看成是值为0的元素，这样问题就转化为后缀求和的问题，再把求和方向调整一下，问题最后就变成了前缀求和。对于前缀求和的问题，已知可以用数据结构Fenwick Tree进行高效求解，其进行一次求前缀和（prefix sum）操作的时间复杂度为\(O(log(n))\)。

综上所述，求解原问题的优化算法为：

1. 对输入数组进行排序，并记录对应下标，复杂度为\(O(nlog(n))\)
2. 构建一颗Fenwick Tree，并以从后向前的方式访问元素数组（把后缀和转为前缀和）。访问时先用sum操作求出前缀和，即当前元素后面比其小的元素总数，然后进行update操作把当前元素标记为已访问。update操作和sum操作的时间复杂度均为\(O(log(n))\)，对n个元素进行则有\(O(nlog(n))\)的时间复杂度

因为步骤一和步骤二的时间复杂度均为\(O(nlog(n))\)，所以总的时间复杂度也为\(O(nlog(n))\)。

代码

class Solution {
public:
	vector<int> countSmaller(vector<int>& nums) {
		vector<int> sorted = nums;
		sort(sorted.begin(), sorted.end());
		map<int, int> record;
		for (int i = 0; i < sorted.size(); i++)
		{
			record[sorted[i]] = i + 1;
		}

		vector<int> fenwickTree = vector<int>(nums.size() + 1, 0);
		vector<int> result;
		for (int i = nums.size() - 1; i >= 0; i--)
		{
			int index = record[nums[i]];
			result.push_back(sum(index - 1, fenwickTree)); // minus one for smaller
			update(index, fenwickTree, 1);
		}

		reverse(result.begin(), result.end());
		return result;
	}

private:
	void update(int index, vector<int>& fenwickTree, int value) {
		for (int i = index; i < fenwickTree.size(); i += i & (-i)) {
			fenwickTree[i] += value;
		}
	}

	int sum(int index, vector<int>& fenwickTree) {
		int sum = 0;
		for (int i = index; i > 0; i -= i & (-i)) {
			sum += fenwickTree[i];
		}
		return sum;
	}
};