给定一个整数数组 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<int> counts(nums.size()); vector<int> trans; if (nums.size() == 0) return counts; trans.push_back(nums[nums.size() - 1]); for (int i = nums.size() - 2; i >= 0; i--) { // 这里二分我们用STL里的就好了 auto it = lower_bound(trans.begin(), trans.end(), nums[i]); counts[i] = it - trans.begin(); trans.insert(it, nums[i]); } return counts; } }; class Solution { public: struct node { int Element; int Nums; int Element_nums; node *Left; node *Right; node(int ele) :Element(ele), Element_nums(1), Nums(0), Left(nullptr), Right(nullptr) {}; node() {}; }; void insert(node* rt, node* p, int& cnt) { while (p != rt) { if (p->Element < rt->Element) { if (rt->Left == nullptr) rt->Left = p; rt->Nums++; rt = rt->Left; } else if (p->Element > rt->Element) { if (rt->Right == nullptr) rt->Right = p; cnt += (rt->Nums + rt->Element_nums); rt = rt->Right; } else if (p->Element == rt->Element) { rt->Element_nums++; cnt += rt->Nums; rt = p; } } } vector<int> countSmaller(vector<int>& nums) { vector<int> counts(nums.size()); if (nums.size() == 0) return counts; node* root = new node(nums[nums.size() - 1]); for (int i = nums.size() - 2; i >= 0; i--) insert(root, new node(nums[i]), counts[i]); return counts; } };