给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
示例:
输入: [5,2,6,1]
输出: [2,1,1,0]
解释:
5 的右侧有 2 个更小的元素 (2 和 1).
2 的右侧仅有 1 个更小的元素 (1).
6 的右侧有 1 个更小的元素 (1).
1 的右侧有 0 个更小的元素.
//分治法
class Solution {
public:
vector<int> countSmaller(vector<int>& nums) {
vector<pair<int,int>> vec;
vector<int> count;
for(int i = 0;i < nums.size();i++)
{
vec.push_back(make_pair(nums[i],i));
count.push_back(0);
}
merget_sort(vec,count);
return count;
}
void merget_sort(vector<pair<int,int>>& vec,vector<int>& count)
{
if(vec.size() < 2)
return;
int mid = vec.size()/2;
vector<pair<int,int>> sub_vec1;
vector<pair<int,int>> sub_vec2;
for(int i = 0;i < mid;i++)
sub_vec1.push_back(vec[i]);
for(int i = mid;i < vec.size();i++)
sub_vec2.push_back(vec[i]);
merget_sort(sub_vec1,count);
merget_sort(sub_vec2,count);
vec.clear();
merget_sort_two_vec(sub_vec1,sub_vec2,vec,count);
}
void merget_sort_two_vec(vector<pair<int,int>>& sub_vec1,vector<pair<int,int>>& sub_vec2,vector<pair<int,int>>& vec,vector<int>& count)
{
int i = 0;
int j = 0;
while(i < sub_vec1.size() && j < sub_vec2.size())
{
if(sub_vec1[i].first <= sub_vec2[j].first)
{
count[sub_vec1[i].second] += j;
vec.push_back(sub_vec1[i]);
i++;
}
else
{
vec.push_back(sub_vec2[j]);
j++;
}
}
for(;i < sub_vec1.size();i++)
{
count[sub_vec1[i].second] += j;
vec.push_back(sub_vec1[i]);
}
for(;j < sub_vec2.size();j++)
{
vec.push_back(sub_vec2[j]);
}
}
};
//二叉搜索树
class Solution {
public:
struct BSTNode{
int val;
int count;
BSTNode* left;
BSTNode* right;
BSTNode(int x):val(x),left(NULL),right(NULL),count(0){}
};
vector<int> countSmaller(vector<int>& nums) {
vector<int> vec;
vector<int> count;
vector<BSTNode*> node_vec;
for(int i = nums.size() - 1;i >= 0;i--)
{
node_vec.push_back(new BSTNode(nums[i]));
}
count.push_back(0);
for(int i = 1;i < node_vec.size();i++)
{
int count_small = 0;
insert(node_vec[0],node_vec[i],count_small);
count.push_back(count_small);
}
for(int i = node_vec.size() - 1;i >= 0;i--)
{
delete node_vec[i];
vec.push_back(count[i]);
}
return vec;
}
void insert(BSTNode* node,BSTNode* insert_node,int &count_small)
{
if(insert_node->val <= node->val)
{
node->count++;
if(node->left)
insert(node->left,insert_node,count_small);
else
node->left = insert_node;
}
else
{
count_small += node->count + 1;
if(node->right)
insert(node->right,insert_node,count_small);
else
node->right = insert_node;
}
}
};
