Rank from Stream: 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). lmplement 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
1
2
3
4
|
Stream (in order of appearance): 5, 1, 4, 4, 5, 9, 7, 13, 3
getRankOfNumber(1) = 0
getRankOfNumber(3) = 1
getRankOfNumber(4) = 3
|
Hints: #301, #376, #392
解法1(不好)
弄三个：
- map 1记录 < x 的数字的数量。这个map按照key升序排。
- map 2 记录x重复的数字的数量。
- map 3 记录 <= x的数字的数量 = < x的数字的数量 + x 重复的数字的数量 - 1。
每次track的时候要遍历map 1，找到在x前面的值。
每次getRankOfNumber的时候直接get map 3就行。
这个做法不太好，因为每次都牵涉到遍历。
解法2
比如弄一个二叉搜索树，左节点 <= 当前节点，右节点 > 当前节点：
1
2
3
4
5
6
7
8
9
10
11
|
5
/ \
1 9
\ / \
4 7 13
/
4
\
5
/
3
|
因为有重复数据，所以我们可以把重复的数量记录在里面：
1
2
3
4
5
6
7
|
5(d=2)
/ \
1(d=1) 9(d=1)
\ / \
4(d=2) 7(d=1) 13(d=1)
/
3(d=1)
|
因为rank = 自己重复数量 - 1 + 比自己小的数字的数量，改写成rank = sel.dups - 1 + sum(smaller.dups)。
sum(smaller.dups)怎么计算的，在二叉搜索树中查找x所经过的路径中的遇到过的比自己小的节点时，sum(其左子树的dups)（含这个节点自身）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
public Node {
private int value;
private Node left;
private Node right;
private int dups;
private int leftSumDups;
public Node(int value) {
this.value = value;
this.dups = 1;
}
public void track(int value) {
if (value == this.value) {
this.dups++;
return;
}
if (value < this.value) {
if (this.left == null) {
this.left = new Node(value);
} else {
this.left.track(value);
this.leftSumDups++;
}
return;
}
if (value > this.value) {
if (this.right == null) {
this.right = new Node(value);
} else {
this.right.track(value);
}
}
}
public int getRankOfNumber(int value) {
if (value == this.value) {
return this.dups - 1 + this.leftSumDups;
}
if (value < this.value && this.left != null) {
return this.left.getRankOfNumber(value);
}
if (value > this.value && this.right != null) {
int rightRank = this.right.getRankOfNumber(value);
if (rightRank == -1) {
return -1;
}
return this.dups + this.leftSumDups + rightRank;
}
return -1;
}
}
|
评论