forked from kamyu104/LintCode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
count-of-smaller-number-before-itself.cpp
86 lines (80 loc) · 2.38 KB
/
count-of-smaller-number-before-itself.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
// Time: O(nlogn)
// Space: O(h)
class Solution {
public:
class BSTreeNode {
public:
int val, count;
BSTreeNode *left, *right;
BSTreeNode(int val, int count) {
this->val = val;
this->count = count;
this->left = this->right = nullptr;
}
};
/**
* @param A: An integer array
* @return: Count the number of element before this element 'ai' is
* smaller than it and return count number array
*/
vector<int> countOfSmallerNumberII(vector<int> &A) {
vector<int> res;
BSTreeNode *root = nullptr;
// Insert into BST and get left count.
for (int i = 0; i < A.size(); ++i) {
int count = 0;
BSTreeNode *node = new BSTreeNode(A[i], 0);
root = insertNode(root, node);
count = query(root, A[i]);
res.emplace_back(count);
}
return res;
}
// Insert node into BST.
BSTreeNode* insertNode(BSTreeNode* root, BSTreeNode* node) {
if (root == nullptr) {
return node;
}
BSTreeNode* curr = root;
while (curr) {
// Insert left if smaller.
if (node->val < curr->val) {
++curr->count; // Increase the number of left children.
if (curr->left != nullptr) {
curr = curr->left;
} else {
curr->left = node;
break;
}
} else { // Insert right if larger or equal.
if (curr->right != nullptr) {
curr = curr->right;
} else {
curr->right = node;
break;
}
}
}
return root;
}
// Query the smaller count of the value.
int query(BSTreeNode* root, int val) {
if (root == nullptr) {
return 0;
}
int count = 0;
BSTreeNode* curr = root;
while (curr) {
// Insert left.
if (val < curr->val) {
curr = curr->left;
} else if (val > curr->val) {
count += 1 + curr->count; // Count the number of the smaller nodes.
curr = curr->right;
} else { // Equal.
return count + curr->count;
}
}
return 0;
}
};