[CC150v5] 11.8 Get Rank in Stream of Integers - Shuatiblog.com
http://xiaochongzhang.me/blog/?p=559
Cpp code: https://github.com/jsc0218/CC150/blob/master/11.8.cpp
Read full article from [CC150v5] 11.8 Get Rank in Stream of Integers - Shuatiblog.com
Imagine you are reading in a stream of integers. Periodically, you wish to be able to look up the rank of a number x (the number of values less than or equal to x).
Implement the data structures and algorithms to support these operations. That is, implement the method track(int x), which is called when each number is generated, and the method getRankOfNumber(int x), which returns the number of values less than or equal to x (not including x itself).
Solution
This question requires a special type of Data Structure. It basically is a modified BST like this:The tree node stores both number value and the count of node on left subtree
http://xiaochongzhang.me/blog/?p=559
struct RankNode
{
RankNode(int val):left_size(0),left(NULL),right(NULL),NodeData(val){}
int left_size;
RankNode* left;
RankNode* right;
int NodeData;
};
class RankNodeTree
{
public:
RankNodeTree():root(NULL){}
void track(int new_Num)
{
if(root == NULL)
root = new RankNode(new_Num);
else
{
insert(new_Num,root);
}
}
void insert(int val,RankNode* head)
{
if(head->NodeData >= val)
{
if(head->left!=NULL)
{
insert(val,head->left);
}
else
{
RankNode* new_Node = new RankNode(val);
head->left = new_Node;
}
++head->left_size;
}
else
{
if(head->right!=NULL)
{
insert(val,head->right);
}
else
{
RankNode* new_Node = new RankNode(val);
head->right = new_Node;
}
}
}
int getRank(int val,RankNode* head)
{
if(val == head->NodeData)
return head->left_size;
else if(val < head->NodeData)
{
if(head->left == NULL)
return -1;
else
return getRank(val,head->left);
}
else
{
int right_rank;
if(head->right == NULL)
{
right_rank = -1;
}
else
{
right_rank = getRank(val,head->right);
}
if(right_rank == -1)
return -1;
else
return head->left_size+1+right_rank;
}
}
RankNode* root;
};
Python code: https://github.com/yyyuaaaan/ctci5th/blob/master/11.8bstcount.pyCpp code: https://github.com/jsc0218/CC150/blob/master/11.8.cpp
Read full article from [CC150v5] 11.8 Get Rank in Stream of Integers - Shuatiblog.com
