315.自己の後のより小さな数の数
315 Count Smaller Numbers After Self
315.自己の後のより小さな数の数
整数配列numsが与えられ、新しいcounts配列を返す必要があります。 counts配列には、counts [i]がnums [i]の右側にある小さい要素の数であるというプロパティがあります。
例：
入力：[5,2,6,1]
出力：[2,1,1,0]
説明：
5の右側には、2つの小さな要素（2と1）があります。
2の右側には、小さい要素が1つだけあります（1）。
6の右側には、1つの小さな要素（1）があります。
1の右側には、0個の小さい要素があります。
グランヤン： https://www.cnblogs.com/grandyang/p/5078490.html
討論： https://leetcode.com/problems/count-of-smaller-numbers-after-self/discuss/76580/9ms-short-Java-BST-solution-get-answer-when-building-BST
考え：
ディスカッションエリアでは、ハイスコアのソリューションを比較します。最悪の場合、[n、n-1、n-2、... 1]がすべてデクリメントされると、ここでのbstは不均衡であるため、複雑さはO（n ^ 2）になります。
本質的にはまだ挿入ソートです。 numを右から左にトラバースし、新しい番号をbstに挿入する場所を探します。また、bstを拡張してsmallerCn（現在のノードよりもいくつ少ないか）を格納できます。 root-> val> valの場合、root-> smallCnt ++で、左側のサブツリーを再帰的に呼び出します。ルート-> valsmallerCntの場合。 root-> val == valの場合、
class Solution { private: struct TreeNode { TreeNode* left, * right int val, smallerCnt TreeNode (int _val, int _sm) { val = _val smallerCnt = _sm left = nullptr right = nullptr } } TreeNode* insert(TreeNode* root, int val, int idx, int presum, vector<int> & res) { if (!root) { TreeNode* node = new TreeNode(val, 0) res[idx] = presum return node } else if (root -> val > val) { root -> smallerCnt++ root -> left = insert(root -> left, val, idx, presum, res) } else { // vital double brackets root -> right = insert(root -> right, val, idx, presum + root -> smallerCnt + ((root -> val < val) ? 1 : 0), res) } return root } public: vector<int> countSmaller(vector<int>& nums) { int n = nums.size() vector<int> res(n, 0) TreeNode* root = nullptr for (int i = n - 1 i >= 0 i--) { root = insert(root, nums[i], i, 0, res) } return res } }