315. 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].
Time Complecity: O(nlogn)
Solution 1: Binary Search Tree (还是这个最好理解)
这道题给定我们一个数组，让我们计算每个数字右边所有小于这个数字的个数，目测我们不能用brute force，OJ肯定不答应，那么我们为了提高运算效率，首先可以使用用二分搜索法，思路是将给定数组从最后一个开始，用二分法插入到一个新的数组，这样新数组就是有序的，那么此时该数字在新数组中的坐标就是原数组中其右边所有较小数字的个数，参见代码如下：
vector<int> countSmaller(vector<int>& nums) {
vector<int> t, res(nums.size());
for (int i = nums.size()-1; i >= 0; --i) {
int left = 0, right = t.size();
while (left < right) { // find insert position
int mid = (left+right)/2;
if (t[mid] >= nums[i]) right = mid;
else left = mid+1;
}
res[i] = right;
t.insert(t.begin()+right, nums[i]);
}
return res;
}
上面使用二分搜索法是一种插入排序的做法，我们还可以用C++中的STL的一些自带的函数来帮助我们，比如求距离distance，或是求第一个不小于当前数字的函数lower_bound，这里利用这两个函数代替了上一种方法中的二分搜索的部分，两种方法的核心思想都是相同的，构造有序数组，找出新加进来的数组在有序数组中对应的位置存入结果中即可，参见代码如下：
vector<int> countSmaller(vector<int>& nums) {
vector<int> t, res(nums.size());
for (int i = nums.size()-1; i >= 0; --i) {
int left = 0, right = t.size();
int d = distance(t.begin(), lower_bound(t.begin(), t.end(), nums[i]));
// int d = lower_bound(t.begin(), t.end(), nums[i]) - t.begin();
res[i] = d;
t.insert(t.begin()+d, nums[i]);
}
return res;
}
Solution 2: Binary Indexed Tree
再来看一种利用二分搜索树来解的方法，我们来构造一棵二分搜索树，稍有不同的地方是我们需要加一个变量smaller来记录比当前节点值小的所有节点的个数，我们每插入一个节点，会判断其和根节点的大小，如果新的节点值小于根节点值，则其会插入到左子树中，我们此时要增加根节点的smaller，并继续递归调用左子节点的insert。如果节点值大于根节点值，则需要递归调用右子节点的insert并加上根节点的smaller，并加1，参见代码如下：
class Solution {
public:
struct Node {
int val, smaller;
Node *left, *right;
Node(int v, int s): val(v), smaller(s), left(NULL), right(NULL) {}
};
int insert(Node *&root, int v) {
if (!root) return (root = new Node(v, 0)), 0;
if (root->val > v) return root->smaller++, insert(root->left, v);
else return insert(root->right, v)+root->smaller+(root->val < v ? 1 : 0); // ==: exclude root
}
vector<int> countSmaller(vector<int>& nums) {
vector<int> res(nums.size());
Node *root = NULL;
for (int i = nums.size()-1; i >= 0; --i) {
res[i] = insert(root, nums[i]);
}
return res;
}
};
Solution 3: MergeSort
MergeSort-based solution is a standard way to solve problems related to inverse numbers.
Here is an example to illustrate the general idea of MergeSort-based algorithm:
Now we want to consider an array
6 4 1 8 7 5 2 9
First thing first, split the array into to subarrays:
6 4 1 8
7 5 2 9
and then calculate the inverse numbers within the group:
1 4(1) 6(1,4) 8
2 5(2) 7(2,5) 9
where the numbers in the parentheses are the numbers that should be counted when we calculate the inverse number.
Now we need to merge these two arrays into one sorted array. The first element to be put into the sorted destination array is the "1" in the first array.
1 4(1) 6(1,4) 8
2 5(2) 7(2,5) 9 merged elements in the 2nd array = ()
The second element to merge is the "2" in the second array:
1 2 4(1) 6(1,4) 8
5(2) 7(2,5) 9 merged elements in the 2nd array = (2)
The third element to merge is the "4" in the first array:
1 2 4(1,2) 6(1,4) 8
5(2) 7(2,5) 9 merged elements in the 2nd array = (2)
When we merge the "4(1)", we found that "4" is actually greater than all merged elements in the second array (i.e. [2]). Therefore, we also need to consider those elements. Therefore, the numbers in the parenthese of 2 become (1)+(2) = (1,2). Next step:
1 2 4(1,2) 5(2) 6(1,4) 8
7(2,5) 9 merged elements in the 2nd array = (2,5)
Next (add the inverse number of element "6" by 2)
1 2 4(1,2) 5(2) 6(1,4,2,5) 8
7(2,5) 9 merged elements in the 2nd array = (2,5)
So and so forth, finally reach
1 2 4(1,2) 5(2) 6(1,4,2,5) 7(2,5) 8(2,5,7) 9
merged elements in the 2nd array = (2,5,7,9)
Additionally, when we need to count the inverse number, we do not need to record the exact elements, we only need to record the numbers. So, we can use a variable to record the number of "merged elements in the 2nd array" (for example,semilenin the code beneath) and the number of smaller elements of each element (for example,results[idx]in the code beneath).
Complexities:
Time: O(n log n)
Space: O(n)
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, idx2 = mid; // idx in two arrays
int semicount = 0;
while ((idx1 < mid) || (idx2 < last)) {
// add elements in first array
if ((idx2 == last) || ((idx1 < mid) && (nums[indices[idx1]] <= nums[indices[idx2]]))) {
tmp.push_back(indices[idx1]);
results[indices[idx1]] += semicount;
++idx1;
} else { // add elements in second array
tmp.push_back(indices[idx2]);
++semicount;
++idx2;
}
}
move(tmp.begin(), tmp.end(), indices.begin()+first);
// Moves the elements in the range [first,last) into the range beginning at result.
// put new orders into indices
}
}
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); // indices[i] = i
merge_countSmaller(indices, 0, n, results, nums);
return results;
}
};