The problem can be restated in this way, find the inverse numbers (i.e. nums[i] > nums[j] but i < j) for each number in the array. There are two ways to solve this problem. First solution is to build a binary search tree from the end to beginning such that a new coming node must have index less than existing node. So the invert number for the new node will be nodes that have value less than it. To do so, we need to modify the tree node a little bit to include left node count and its own copy (for duplicate nodes). So for a new coming number, there are 3 cases:
Case 1: root value is equal to the new value, i.e. a duplicated node is found.
We just increase the root's copy and return the left count of root.
Case 2: root value is less than the new value.
We need to increase the left count of root and insert the new node to left and return the new node's left count.
Case 3: root value is larger than the new value.
We need to insert the new node to right and return root's left count plus root's own copy plus the new node's left count.
From the three cases above, we can see that we need to return the left count for insert operation.
1: class Node {
2: public:
3: int val, copy, leftCount;
4: Node *left, *right;
5: Node(int x) { val = x; copy = 1; leftCount = 0; left = NULL; right = NULL; }
6: };
7: class Solution {
8: public:
9: vector<int> countSmaller(vector<int>& nums) {
10: int n = nums.size();
11: vector<int> res(n, 0);
12: if (nums.size() <= 1) return res;
13: Node *root = new Node(nums[nums.size()-1]);
14: for (int i = nums.size()-2; i >= 0; i--) {
15: res[i] = insert(root, nums[i]);
16: }
17: return res;
18: }
19: int insert(Node *root, int val) {
20: if (root->val == val) {
21: root->copy++;
22: return root->leftCount;
23: } else if (root->val > val) {
24: root->leftCount++;
25: if (root->left) {
26: return insert(root->left, val);
27: } else {
28: root->left = new Node(val);
29: return 0;
30: }
31: } else {
32: if (root->right) {
33: return root->leftCount+root->copy+insert(root->right, val);
34: } else {
35: root->right = new Node(val);
36: return root->leftCount+root->copy;
37: }
38: }
39: }
40: };
When I revisited this problem, I made mistakes in:
line 16: I was returning 1 instead of 0.
line 27: I wasn't aware that there is no smaller number if the input array only contains one number.
line 29: I wasn't aware that I should have started from the end.
1: class MyTreeNode {
2: public:
3: int val;
4: int copy;
5: int leftCounts;
6: MyTreeNode *left;
7: MyTreeNode *right;
8: MyTreeNode(int x): val(x), copy(1), leftCounts(0), left(NULL), right(NULL) {}
9: };
10: class Solution {
11: private:
12: int insert(MyTreeNode *root, int val) {
13: if (root->val == val) { root->copy++; return root->leftCounts; }
14: if (root->val > val) {
15: root->leftCounts++;
16: if (root->left == NULL) { root->left = new MyTreeNode(val); return 0;}
17: else return insert(root->left, val);
18: } else {
19: if (root->right == NULL) { root->right = new MyTreeNode(val); return root->leftCounts + root->copy; }
20: else return root->leftCounts + root->copy + insert(root->right, val);
21: }
22: }
23: public:
24: vector<int> countSmaller(vector<int>& nums) {
25: int n = nums.size();
26: vector<int> res = vector<int>(n, 0);
27: if (n < 2) return res;
28: MyTreeNode *root = new MyTreeNode(nums[n-1]);
29: for (int i = n-2; i >= 0; i--) {
30: res[i] = insert(root, nums[i]);
31: }
32: return res;
33: }
34: };
Another way is to do merge sort.
