Two different solutions using BST and MergeSort in C++, both accepted as best

• ``````class Solution
{
private:
void insert(Node* root, int val, int& lessCount)
{
int curVal = root->val;
if(val < curVal)
{
root->lessCount++; //only consider the nodes inserted afterwards;
if(!root->left) root->left = new Node(val);
else insert(root->left, val, lessCount);
}
else if(val > curVal)
{
lessCount += root->lessCount + root->count; //using += instead of =;
if(!root->right) root->right = new Node(val);
else insert(root->right, val, lessCount);
}
else
{
lessCount += root->lessCount; //using += instead of =;
root->count++;
}
}
public:
//AC - 36ms - using BST to accelerate;
vector<int> countSmaller(vector<int>& nums)
{
int size = nums.size();
if(!size) return vector<int>();
vector<int> counters(size, 0);
Node *root = new Node(nums[size-1]);
for(int i = size-2; i > -1; i--)
insert(root, nums[i], counters[i]);
return counters;
}
};
``````

``````class Solution
{
private:
void merge(vector<int>& nums, int l, int r, vector<int>& index0, vector<int>& index1, vector<int>& v)
{
if(l == r) return ;
int m = l+(r-l)/2;
merge(nums, l, m, index0, index1, v);
merge(nums, m+1, r, index0, index1, v);
int i=l, j=m+1, k=l;
while(i<=m || j<=r)
{
if((i<=m && j<=r && nums[index0[i]]<=nums[index0[j]]) || j>r)
{
index1[k++] = index0[i];
v[index0[i]] += j-m-1; //how many have been collected first in the right part;
i++;
}
else index1[k++] = index0[j++];
}
for(int i = l; i <= r; i++) index0[i] = index1[i]; //update index0 for later use;
}
public:
//AC - 44ms - merge sort, a stable sorting method;
vector<int> countSmaller(vector<int>& nums)
{
int size = nums.size();
if(!size) return vector<int>();
vector<int> index0, index1; //record the indexes of the numbers;
for(int i = 0; i < size; i++) index0.push_back(i), index1.push_back(i);
vector<int> v(size, 0);
merge(nums, 0, size-1, index0, index1, v);
return v;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.