Give you an integer array (index from 0 to n-1, where n is the size of this array, data value from 0 to 10000) . For each elementAiin the array, count the number of element before this elementAiis smaller than it and return count number array.
Notice
We suggest you finish problemSegment Tree Build,Segment Tree Query IIandCount of Smaller Numberfirst.
Have you met this question in a real interview?
Yes
Example
For array[1,2,7,8,5], return[0,1,2,3,2]
line 17 val = 0 case
line 56 need return here
class Solution {
public:
/**
\* @param A: An integer array
\* @return: Count the number of element before this element 'ai' is
\* smaller than it and return count number array
\*/
vector<int> countOfSmallerNumberII\(vector<int> &A\) {
// write your code here
vector<int> res;
SegmentTreeNode\* root = buildSegmentTree\(0, 10000\);
for \(int val : A\) {
int cnt = 0;
if \(val > 0\) {
cnt = query\(root, 0, val - 1\);
}
modifySegmentTree\(root, val, 1\);
res.push\_back\(cnt\);
}
return res;
}
class SegmentTreeNode {
public:
int start, end, count;
SegmentTreeNode \*left, \*right;
SegmentTreeNode\(int start, int end, int count\) : start\(start\), end\(end\), count\(count\), left\(NULL\), right\(NULL\){}
};
SegmentTreeNode\* buildSegmentTree\(int start, int end\) {
if \(start == end\) {
return new SegmentTreeNode\(start, end, 0\);
}
int mid = start + \(end - start >> 1\);
SegmentTreeNode\* root = new SegmentTreeNode\(start, end, 0\);
root->left = buildSegmentTree\(start, mid\);
root->right = buildSegmentTree\(mid + 1, end\);
root->count = root->left->count + root->right->count;
return root;
}
int query\(SegmentTreeNode\* root, int start, int end\) {
if \(root->start > end \|\| root->end < start\) {
return 0;
}
if \(start <= root->start && root->end <= end\) {
return root->count;
}
return query\(root->left, start, end\) + query\(root->right, start, end\);
}
void modifySegmentTree\(SegmentTreeNode\* root, int index , int value\) {
if \(root->start == root->end && index == root->start\) {
root->count += value;
return;
}
if \(root->start <= index && index <= root->end\) {
modifySegmentTree\(root->left, index, value\);
modifySegmentTree\(root->right, index, value\);
root->count = root->left->count + root->right->count;
}
}
};