This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
public: | |
vector<int> countSmaller(vector<int>& nums) { | |
int len = nums.size(); | |
vector<int> idx(len, 0), res(len, 0); | |
for(int i = 0; i < len; ++i) | |
idx[i] = i; | |
mergeSort(nums, idx, res, 0, len - 1); | |
return res; | |
} | |
private: | |
void mergeSort(vector<int>& nums, vector<int>& idx, vector<int>& res, int lo, int hi) | |
{ | |
if(lo >= hi)return; | |
int mid = lo + (hi - lo) / 2; | |
mergeSort(nums, idx, res, lo, mid); | |
mergeSort(nums, idx, res, mid + 1, hi); | |
int p1 = lo, p2 = mid + 1; | |
vector<int> aux(hi - lo + 1, 0); | |
int curr = 0; | |
while(p1 <= mid && p2 <= hi) | |
{ | |
int idx1 = idx[p1], idx2 = idx[p2], num1 = nums[idx1], num2 = nums[idx2]; | |
if(num1 <= num2) | |
{ | |
res[idx1] += p2 - mid - 1; | |
aux[curr++] = idx[p1++]; | |
} | |
else | |
{ | |
aux[curr++] = idx[p2++]; | |
} | |
} | |
while(p1 <= mid) | |
{ | |
res[idx[p1]] += p2 - mid - 1; | |
aux[curr++] = idx[p1++]; | |
} | |
while(p2 <= hi) | |
aux[curr++] = idx[p2++]; | |
for(int i = lo; i <= hi; ++i) | |
idx[i] = aux[i - lo]; | |
} | |
}; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
struct Node | |
{ | |
int key, size, dup; | |
Node* left, *right; | |
Node(int num) : key(num), size(1), dup(1), left(nullptr), right(nullptr) | |
{ | |
} | |
}; | |
class Solution { | |
public: | |
vector<int> countSmaller(vector<int>& nums) { | |
int len = nums.size(); | |
vector<int> res(len, 0); | |
for(int i = len - 1; i >= 0; --i) | |
{ | |
res[i] = search(m_root, nums[i]); | |
insert(nums[i]); | |
} | |
return res; | |
} | |
private: | |
Node* m_root; | |
int size(Node* root) | |
{ | |
return root? root->size: 0; | |
} | |
int search(Node* curr, int key) | |
{ | |
if(!curr)return 0; | |
if(curr->key < key)return curr->dup + size(curr->left) + search(curr->right, key); | |
else if(curr->key >= key)return search(curr->left, key); | |
} | |
void insert(int key) | |
{ | |
if(m_root == nullptr) | |
{ | |
m_root = new Node(key); | |
return; | |
} | |
Node* curr = m_root; | |
while(true) | |
{ | |
++curr->size; | |
if(curr->key < key) | |
{ | |
if(curr->right)curr = curr->right; | |
else | |
{ | |
curr->right = new Node(key); | |
break; | |
} | |
} | |
else if(curr->key > key) | |
{ | |
if(curr->left)curr = curr->left; | |
else | |
{ | |
curr->left = new Node(key); | |
break; | |
} | |
} | |
else | |
{ | |
++curr->dup; | |
break; | |
} | |
} | |
} | |
}; |
Segment Tree:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Node | |
{ | |
public: | |
int start, end; | |
int cnt;//# of nums appear in [start, end] | |
Node* left, *right; | |
Node(int s, int e) | |
{ | |
start = s; | |
end = e; | |
cnt = 0; | |
left = nullptr; | |
right = nullptr; | |
} | |
Node* getLeft() | |
{ | |
int mid = start + (end - start) / 2; | |
if (!left)left = new Node(start, mid); | |
return left; | |
} | |
Node* getRight() | |
{ | |
int mid = start + (end - start) / 2; | |
if (!right)right = new Node(mid + 1, end); | |
return right; | |
} | |
void insert(int key) | |
{ | |
if (start == end) | |
{ | |
++cnt; | |
return; | |
} | |
int mid = start + (end - start) / 2; | |
if (key <= mid)getLeft()->insert(key); | |
else getRight()->insert(key); | |
cnt = getLeft()->cnt + getRight()->cnt; | |
} | |
//how many nums we have in [s, e] | |
int query(int s, int e) | |
{ | |
if (s > end || e < start)return 0; | |
else if (start >= s && end <= e)return cnt; | |
else return getLeft()->query(s, e) + getRight()->query(s, e); | |
} | |
void clear() | |
{ | |
if(left)left->clear(); | |
if(right)right->clear(); | |
delete this; | |
} | |
}; | |
class Solution { | |
public: | |
vector<int> countSmaller(vector<int>& nums) { | |
int len = nums.size(); | |
//mapping to index | |
vector<int> aux = nums; | |
sort(aux.begin(), aux.end()); | |
unordered_map<int, int> map; | |
for (int i = 0; i < len; ++i)map[aux[i]] = i; | |
Node* root = new Node(0, len - 1); | |
vector<int> res; | |
for (int i = len - 1; i >= 0; --i) | |
{ | |
int ans = root->query(0, map[nums[i]] - 1); | |
root->insert(map[nums[i]]); | |
res.push_back(ans); | |
} | |
reverse(res.begin(), res.end()); | |
return res; | |
} | |
}; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class BIT | |
{ | |
public: | |
BIT(int n) | |
{ | |
N = n + 1; | |
tree = vector<int>(N, 0); | |
} | |
void insert(int key) | |
{ | |
int i = key + 1; | |
while(i < N) | |
{ | |
++tree[i]; | |
i += i & -i; | |
} | |
} | |
int queryUntil(int key) | |
{ | |
int i = key + 1, res = 0; | |
while(i) | |
{ | |
res += tree[i]; | |
i -= i & -i; | |
} | |
return res; | |
} | |
private: | |
int N; | |
vector<int> tree; | |
}; | |
class Solution { | |
public: | |
vector<int> countSmaller(vector<int>& nums) { | |
int len = nums.size(); | |
//mapping to index | |
vector<int> aux = nums; | |
sort(aux.begin(), aux.end()); | |
unordered_map<int, int> map; | |
for (int i = 0; i < len; ++i)map[aux[i]] = i; | |
BIT bit(len); | |
vector<int> res; | |
for(int i = len - 1; i >= 0; --i) | |
{ | |
int ans = bit.queryUntil(map[nums[i]] - 1); | |
res.push_back(ans); | |
bit.insert(map[nums[i]]); | |
} | |
reverse(res.begin(), res.end()); | |
return res; | |
} | |
}; |
No comments:
Post a Comment