給定一個整數(shù)數(shù)組 nums，按要求返回一個新數(shù)組?counts。數(shù)組 counts 有該性質(zhì)： counts[i] 的值是? nums[i] 右側(cè)小于?nums[i] 的元素的數(shù)量。
示例:
輸入: [5,2,6,1]
輸出: [2,1,1,0]
解釋:
5 的右側(cè)有 2 個更小的元素 (2 和 1).
2 的右側(cè)僅有 1 個更小的元素 (1).
6 的右側(cè)有 1 個更小的元素 (1).
1 的右側(cè)有 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;
????????}
????}
};
