j******8
发帖数: 105 | 1 设计一个数据结构，包括两个操作
void insert(int d): 插入一个int
int query(int d): 查询d在数据结构中的排名
example:
Insert: 4, 5, 3
query(4) gives 2;
insert: 1
query(4) gives 3;
如何设计保证两个操作都是O(log(n))? |
s*******g
发帖数: 22 | |
a********5
发帖数: 1631 | 3 BST带RANK。每个接点存一个INT做RANK，表示这个节点左子树大小。
插入的时候在找插入位置的过程中，如果当前节点要往左走，则把当前节点的RANK加一。
查询的时候，在查找元素的过程中，如果当前节点要往右走，累加当前节点的RANK。 |
j******8
发帖数: 105 | 4 Thanks a lot !
I'm too weak to see this solution...
一。
【在 a********5 的大作中提到】
: BST带RANK。每个接点存一个INT做RANK，表示这个节点左子树大小。
: 插入的时候在找插入位置的过程中，如果当前节点要往左走，则把当前节点的RANK加一。
: 查询的时候，在查找元素的过程中，如果当前节点要往右走，累加当前节点的RANK。
|
x*****a
发帖数: 610 | 5 加RANK这个想法是对的
但是普通BST不可
普通BST无法保证查找一定是O(log(n))。最坏情况可能是O(n)。
如果题目要求是“保证O(log(n))”
就必须用self-balancing BST， 比如红黑树。
不过我不认为这世界上有几个人能不看任何资料在短时间内写出红黑树的插入算法
所以这题应该说说就行，不用真写code
一。
【在 a********5 的大作中提到】
: BST带RANK。每个接点存一个INT做RANK，表示这个节点左子树大小。
: 插入的时候在找插入位置的过程中，如果当前节点要往左走，则把当前节点的RANK加一。
: 查询的时候，在查找元素的过程中，如果当前节点要往右走，累加当前节点的RANK。
|
d*********e
发帖数: 352 | |
j********r
发帖数: 127 | 7 不怕浪费空间或者已知输入范围的话，用线段树segment tree
操作是O(logK) k是数据范围
每个节点存节点下所有有值节点数目，然后求区域极小值到当前值之间区域的所有点数
【在 j******8 的大作中提到】
: 设计一个数据结构，包括两个操作
: void insert(int d): 插入一个int
: int query(int d): 查询d在数据结构中的排名
: example:
: Insert: 4, 5, 3
: query(4) gives 2;
: insert: 1
: query(4) gives 3;
: 如何设计保证两个操作都是O(log(n))?
|
