[CareerCup] 11.8 The Rank of Number 数的排行 - Grandyang - 博客园
11.8 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 tox). 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).
EXAMPLE
Stream (in order of appearance): 5, 1, 4, 4, 5, 9, 7, 13, 3
getRankOfNumber(l) = 0
getRankOfNumber(3) = 1
getRankOfNumber(4) = 3
这道题给了我们一个无序数组，让我们求每个数字的排行，排行为几就表示有几个小于或等于该数字的数。我们首先需要用一个数据结构来保存有序数组，用向量的话加数字不高效，用priority_queue或者multiset的话求rank又太麻烦，引文不能直接通过坐标访问元素。那么我们考虑用另一种有序的数据结构，二叉搜索树Binary Search Tree，我们知道BST的性质是左<=中<右，中序遍历一个BST的结果就是有序数组。为了更有效的找出rank，我们在加入新数字的时候，记录一个变量left_size，表示此数字的左子树的节点数。我们来看下面这个例子，每个节点表示当前数字，括号中的数字表示当前节点的左子节点的个数。
Read full article from [CareerCup] 11.8 The Rank of Number 数的排行 - Grandyang - 博客园
No comments:
Post a Comment