LeetCode Q315: Count of Smaller Numbers After Self (hard)

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Given nums = [5, 2, 6, 1]

To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

Return the array [2, 1, 1, 0].

Solution:

I refer to this post for a solution using  BST. The basic idea is to use node in a tree to save information about how many nodes met already are smaller. 

I actually tried several solutions and for both of them I use node to save the number of nodes that appear after current node. However, saving information in this way force you have to update subtree of current when a node that is smaller than current node. This results in a TLE.

Instead, we should use node to save how many nodes are in the left of current node, which will not require an update of subtree.

	class Solution {
	struct TreeNode {
	int val;
	int sum;
	int dup;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int v, int s) : val(v), sum(s), dup(1), left(NULL), right(NULL) {}
	};
	public:
	TreeNode* insert(int num, TreeNode* node, vector<int>& res, int i , int preSum){
	if(node == NULL){
	node = new TreeNode(num, 0);
	res[i] = preSum;
	} else if(node->val == num){
	node->dup++;
	res[i]=preSum + node->sum;
	} else if(node->val > num){
	node->sum++;
	node->left = insert(num, node->left, res, i, preSum);
	} else {
	node->right = insert(num, node->right, res, i, preSum+node->dup+node->sum);
	}
	return node;
	}
	vector<int> countSmaller(vector<int>& nums) {
	vector<int> res(nums.size());
	TreeNode* root = NULL;
	for(int i=nums.size()-1; i>=0; i--)
	root = insert(nums[i], root, res, i, 0);
	return res;
	}
	};

view raw Q315.cpp hosted with ❤ by GitHub

Using mergesort, please refer to this post, and also geeksforgeeks's post. Code is given below:

	class Solution {
	protected:
	void merge_countSmaller(vector<int>& indices, int first, int last,
	vector<int>& results, vector<int>& nums) {
	int count = last - first;
	if (count > 1) {
	int step = count / 2;
	int mid = first + step;
	merge_countSmaller(indices, first, mid, results, nums);
	merge_countSmaller(indices, mid, last, results, nums);
	vector<int> tmp;
	tmp.reserve(count);
	int idx1 = first;
	int idx2 = mid;
	int semicount = 0;
	while ((idx1 < mid) || (idx2 < last)) {
	if ((idx2 == last) || ((idx1 < mid) &&
	(nums[indices[idx1]] <= nums[indices[idx2]]))) {
	tmp.push_back(indices[idx1]);
	results[indices[idx1]] += semicount;
	++idx1;
	} else {
	tmp.push_back(indices[idx2]);
	++semicount;
	++idx2;
	}
	}
	move(tmp.begin(), tmp.end(), indices.begin()+first);
	}
	}
	public:
	vector<int> countSmaller(vector<int>& nums) {
	int n = nums.size();
	vector<int> results(n, 0);
	vector<int> indices(n, 0);
	iota(indices.begin(), indices.end(), 0);
	merge_countSmaller(indices, 0, n, results, nums);
	return results;
	}
	};

view raw Q315-2.cpp hosted with ❤ by GitHub

Using binary indexed tree:
可以使用BIT来解这道题。 假设我们的输入数组是nums={5, 6, 3, 2}, 我们同样从数组的最后一项开始处理。第一个拿出来的是[2]。 我们希望，可以通过BIT的add操作加一个数字1到所有在[2]左边且比[2]大的数中去。可是我们如何才能知道哪些数是比[2]大的呢？ 这个就需要我们对原数组先进行一次排序， 排序后我们得到sorted_nums={2, 3, 5, 6}, 而我们的目的是得到原数组元素在排序后数组的位置places={2, 3, 1, 0}。到此位置，sorted_nums的任务就结束了，我们在程序中就用不到它了。继续我们的操作，此时我们取出来的是[2]， 然后我们找到它在places中对应位置的数[0]。 我们对[0]调用一次add操作(意义在于，我们希望对排序后比[2]大的数据都加1。也就是对排序后排在1, 2, 4位的数都加1， 这里没有3是因为BIT add 操作的原理，之后在算range_query的时候3就等于1+2的内容）。 然后我们就可以调用sum操作计算[2]这个位置的答案了。 之后拿出来的[3], [6]，都可以作同样的操作。 下一位拿出来的是[5], 此时，[5]的places值是2， 那么要向排序后排在[5]之后的数字加1，也就是向排在第2位之后的数字加1。这样的话，我们可能会要向[6]这个位置的加1, 可是这个时候我们不用担心结果出错，因为[6]这个位置的数我们已经处理结束了，即使可能向它加1，我们在处理5的sum操作的时候也只会看[5]排序后位置之前的数字。

	class Solution {
	vector<int> bit;
	public:
	vector<int> countSmaller(vector<int>& nums) {
	vector<int> result(nums.size(), 0);
	bit.resize(nums.size()+1, 0);
	//get the ordered-index-array
	vector<int> sorted_nums(nums);
	vector<int> places(nums.size(), 0);
	sort(sorted_nums.begin(), sorted_nums.end());
	for (int i = 0; i < nums.size(); ++i) {
	places[i] = lower_bound(sorted_nums.begin(), sorted_nums.end(), nums[i]) - sorted_nums.begin();
	cout<<i<<"th places:"<<places[i]<<endl;
	}
	for(int i=places.size()-1; i>=0; i--){
	result[i]=bit_sum(places[i]-1);
	bit_add(places[i], 1);
	}
	return result;
	}
	int bit_last(int i){
	return i&-i;
	}
	void bit_add(int i, int val){
	i++;
	while(i<bit.size()){
	bit[i]+=val;
	i=i+bit_last(i);
	}
	}
	int bit_sum(int i){
	i++;
	int sum=0;
	while(i>0){
	sum+=bit[i];
	i=i-bit_last(i);
	}
	return sum;
	}
	};

view raw Q315-3.cpp hosted with ❤ by GitHub