Haker Rank Median...# JobHunting - 待字闺中
d*x
1 楼
那题目貌似就没卡复杂度。。。枉我昨天下班后还捏着鼻子写了个treap。。。结果证
明是输出格式错了，只过了两三个case的可以考虑检查一下输出格式
思路大致就是用order statistics tree。每次查询都是O(logn)。手写最大问题在于没
法定制容器的行为。。。
好吧，然后想了一下，如果用两个heap加一个map的话也是可以的，因为只是查询
median，没有要求随机查询kth元素，所以还是写复杂了
附上代码，treap是个随机平衡树，可以拿去用。
#include
#include
#include
#include
using namespace std;
template
class Treap {
public:
class Node {
public:
Node(const T& value)
: value_(value),
left_(NULL),
right_(NULL),
parent_(NULL),
count_(1)
{
rank_ = rand();
}
int getCount() {return count_;}
T getValue() {return value_;}
void updateCount() {
int leftCount = left_?left_->count_:0;
int rightCount = right_?right_->count_:0;
count_ = leftCount + rightCount + 1;
}
friend class Treap;
private:
Node* parent_;
Node* left_;
Node* right_;
int count_;
int rank_;
T value_;
};
void rightRotate(Node* node) {
Node* grand = node->parent_->parent_;
Node* right = node->right_;
Node* left = node->left_;
Node* parent = node->parent_;
node->right_ = parent;
node->parent_ = grand;
parent->left_ = right;
parent->parent_ = node;
if (grand) {
if (grand->left_ == parent) {
grand->left_ = node;
} else {
grand->right_ = node;
}
} else {
root_ = node;
}
if (right) {
right->parent_ = parent;
}
parent->updateCount();
node->updateCount();
}
void leftRotate(Node* node) {
Node* grand = node->parent_->parent_;
Node* right = node->right_;
Node* left = node->left_;
Node* parent = node->parent_;
node->left_ = parent;
node->parent_ = grand;
parent->right_ = left;
parent->parent_ = node;
if (grand) {
if (grand->left_ == parent) {
grand->left_ = node;
} else {
grand->right_ = node;
}
} else {
root_ = node;
}
if (left) {
left->parent_ = parent;
}
parent->updateCount();
node->updateCount();
}
Treap() {root_ = NULL;}
void insert(const T& value) {
Node* node = new Node(value);
Node* root = root_;
if (root == NULL) {
root_ = node;
return;
}
while(true) {
if (value < root->value_) {
root->count_++;
if (root->left_ == NULL) {
root->left_ = node;
node->parent_ = root;
break;
}
root = root->left_;
} else {
root->count_++;
if (root->right_ == NULL) {
root->right_ = node;
node->parent_ = root;
break;
}
root = root->right_;
}
}
while(node->parent_ != NULL && node->rank_ > node->parent_->rank_) {
if (node == node->parent_->left_) {
rightRotate(node);
} else {
leftRotate(node);
}
}
}
bool remove(const T& value) {
Node* node = find(value);
if (!node) {
return false;
}
while(node->left_ || node->right_) {
int rightRank = node->right_?node->right_->rank_:-1;
int leftRank = node->left_?node->left_->rank_:-1;
if (leftRank > rightRank) {
rightRotate(node->left_);
} else {
leftRotate(node->right_);
}
}
Node* parent = node->parent_;
if (!parent) {
root_ = NULL;
} else if (node == parent->left_) {
parent->left_ = NULL;
} else {
parent->right_ = NULL;
}
while(parent != NULL) {
parent->count_--;
parent = parent->parent_;
}
delete node;
return true;
}
Node* find(const T& value) {
Node* root = root_;
while(root != NULL) {
if (value == root->value_) {
return root;
} else if (value < root->value_) {
root = root->left_;
} else {
root = root->right_;
}
}
return root;
}
double findMedian() {
if (!root_) {
return -1;
}
int count = root_->count_;
if (count % 2) {
return findKth(count/2 + 1);
} else {
return ((double)findKth(count/2) + (double)findKth(count/2+1))/2;
}
}
T findKth(int k) {
Node* root = root_;
int leftCount = root->left_?root->left_->count_:0;
while(k != leftCount + 1) {
if (k > leftCount + 1) {
k = k - leftCount - 1;
root = root->right_;
} else {
root = root->left_;
}
leftCount = root->left_?root->left_->count_:0;
}
return root->value_;
}
void dump() {
cout << "-----------" << endl;
queue Q;
Q.push(root_);
Node* last = root_;
Node* newLast;
while(!Q.empty()) {
Node* cur = Q.front();
Q.pop();
if (cur->left_ != NULL) {
newLast = cur->left_;
Q.push(cur->left_);
}
if (cur->right_ != NULL) {
newLast = cur->right_;
Q.push(cur->right_);
}
cout << cur->value_ << "(" << cur->rank_ <parent_?
" ":"! ");
if (cur == last) {
last = newLast;
cout << endl;
}
}
cout << "-----------" << endl;
}
bool isEmpty() {
return root_ == NULL;
}
void outputMedian() {
cout.precision(1);
double median = findMedian();
if ((T)median == median) {
cout << (T)median << "\n";
} else {
cout << fixed << median << "\n";
}
}
private:
Node* root_;
};
int main(){
//Helpers for input and output
Treap treap;
int N;
cin >> N;
string s[N];
int x[N];
for(int i = 0; i < N; i++){
cin >> s[i] >> x[i];
if (s[i] == "r") {
bool result = treap.remove(x[i]);
if (!result || treap.isEmpty()) {
cout << "Wrong!\n";
} else {
treap.outputMedian();
}
} else if (s[i] == "a") {
treap.insert(x[i]);
treap.outputMedian();
}
}
return 0;
}
明是输出格式错了，只过了两三个case的可以考虑检查一下输出格式
思路大致就是用order statistics tree。每次查询都是O(logn)。手写最大问题在于没
法定制容器的行为。。。
好吧，然后想了一下，如果用两个heap加一个map的话也是可以的，因为只是查询
median，没有要求随机查询kth元素，所以还是写复杂了
附上代码，treap是个随机平衡树，可以拿去用。
#include
#include
#include
#include
using namespace std;
template
class Treap {
public:
class Node {
public:
Node(const T& value)
: value_(value),
left_(NULL),
right_(NULL),
parent_(NULL),
count_(1)
{
rank_ = rand();
}
int getCount() {return count_;}
T getValue() {return value_;}
void updateCount() {
int leftCount = left_?left_->count_:0;
int rightCount = right_?right_->count_:0;
count_ = leftCount + rightCount + 1;
}
friend class Treap
private:
Node* parent_;
Node* left_;
Node* right_;
int count_;
int rank_;
T value_;
};
void rightRotate(Node* node) {
Node* grand = node->parent_->parent_;
Node* right = node->right_;
Node* left = node->left_;
Node* parent = node->parent_;
node->right_ = parent;
node->parent_ = grand;
parent->left_ = right;
parent->parent_ = node;
if (grand) {
if (grand->left_ == parent) {
grand->left_ = node;
} else {
grand->right_ = node;
}
} else {
root_ = node;
}
if (right) {
right->parent_ = parent;
}
parent->updateCount();
node->updateCount();
}
void leftRotate(Node* node) {
Node* grand = node->parent_->parent_;
Node* right = node->right_;
Node* left = node->left_;
Node* parent = node->parent_;
node->left_ = parent;
node->parent_ = grand;
parent->right_ = left;
parent->parent_ = node;
if (grand) {
if (grand->left_ == parent) {
grand->left_ = node;
} else {
grand->right_ = node;
}
} else {
root_ = node;
}
if (left) {
left->parent_ = parent;
}
parent->updateCount();
node->updateCount();
}
Treap() {root_ = NULL;}
void insert(const T& value) {
Node* node = new Node(value);
Node* root = root_;
if (root == NULL) {
root_ = node;
return;
}
while(true) {
if (value < root->value_) {
root->count_++;
if (root->left_ == NULL) {
root->left_ = node;
node->parent_ = root;
break;
}
root = root->left_;
} else {
root->count_++;
if (root->right_ == NULL) {
root->right_ = node;
node->parent_ = root;
break;
}
root = root->right_;
}
}
while(node->parent_ != NULL && node->rank_ > node->parent_->rank_) {
if (node == node->parent_->left_) {
rightRotate(node);
} else {
leftRotate(node);
}
}
}
bool remove(const T& value) {
Node* node = find(value);
if (!node) {
return false;
}
while(node->left_ || node->right_) {
int rightRank = node->right_?node->right_->rank_:-1;
int leftRank = node->left_?node->left_->rank_:-1;
if (leftRank > rightRank) {
rightRotate(node->left_);
} else {
leftRotate(node->right_);
}
}
Node* parent = node->parent_;
if (!parent) {
root_ = NULL;
} else if (node == parent->left_) {
parent->left_ = NULL;
} else {
parent->right_ = NULL;
}
while(parent != NULL) {
parent->count_--;
parent = parent->parent_;
}
delete node;
return true;
}
Node* find(const T& value) {
Node* root = root_;
while(root != NULL) {
if (value == root->value_) {
return root;
} else if (value < root->value_) {
root = root->left_;
} else {
root = root->right_;
}
}
return root;
}
double findMedian() {
if (!root_) {
return -1;
}
int count = root_->count_;
if (count % 2) {
return findKth(count/2 + 1);
} else {
return ((double)findKth(count/2) + (double)findKth(count/2+1))/2;
}
}
T findKth(int k) {
Node* root = root_;
int leftCount = root->left_?root->left_->count_:0;
while(k != leftCount + 1) {
if (k > leftCount + 1) {
k = k - leftCount - 1;
root = root->right_;
} else {
root = root->left_;
}
leftCount = root->left_?root->left_->count_:0;
}
return root->value_;
}
void dump() {
cout << "-----------" << endl;
queue
Q.push(root_);
Node* last = root_;
Node* newLast;
while(!Q.empty()) {
Node* cur = Q.front();
Q.pop();
if (cur->left_ != NULL) {
newLast = cur->left_;
Q.push(cur->left_);
}
if (cur->right_ != NULL) {
newLast = cur->right_;
Q.push(cur->right_);
}
cout << cur->value_ << "(" << cur->rank_ <parent_?
" ":"! ");
if (cur == last) {
last = newLast;
cout << endl;
}
}
cout << "-----------" << endl;
}
bool isEmpty() {
return root_ == NULL;
}
void outputMedian() {
cout.precision(1);
double median = findMedian();
if ((T)median == median) {
cout << (T)median << "\n";
} else {
cout << fixed << median << "\n";
}
}
private:
Node* root_;
};
int main(){
//Helpers for input and output
Treap
int N;
cin >> N;
string s[N];
int x[N];
for(int i = 0; i < N; i++){
cin >> s[i] >> x[i];
if (s[i] == "r") {
bool result = treap.remove(x[i]);
if (!result || treap.isEmpty()) {
cout << "Wrong!\n";
} else {
treap.outputMedian();
}
} else if (s[i] == "a") {
treap.insert(x[i]);
treap.outputMedian();
}
}
return 0;
}
