10.10.数据流的秩

面试题 10.10. 数字流的秩

Difficulty: **假设你正在读取一串整数。每隔一段时间，你希望能找出数字 x 的秩(小于或等于 x 的值的个数)。请实现数据结构和算法来支持这些操作，也就是说： 实现 track(int x) 方法，每读入一个数字都会调用该方法； 实现 getRankOfNumber(int x) 方法，返回小于或等于 x 的值的个数。 注意：本题相对原题稍作改动 示例: 输入: [“StreamRank”, “getRankOfNumber”, “track”, “getRankOfNumber”] [[], [1], [0], [0]] 输出: [null,0,null,1] 提示： x <= 50000 track 和 getRankOfNumber 方法的调用次数均不超过 2000 次 **

假设你正在读取一串整数。每隔一段时间，你希望能找出数字 x 的秩(小于或等于 x 的值的个数)。请实现数据结构和算法来支持这些操作，也就是说：

实现 track(int x) 方法，每读入一个数字都会调用该方法；

实现 getRankOfNumber(int x) 方法，返回小于或等于 x 的值的个数。

**注意：**本题相对原题稍作改动

示例:

1
2
3
4
5

输入:
["StreamRank", "getRankOfNumber", "track", "getRankOfNumber"]
[[], [1], [0], [0]]
输出:
[null,0,null,1]

提示：

  • x <= 50000
  • track 和 getRankOfNumber 方法的调用次数均不超过 2000 次

Solution

Language: ****

 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

type  Tree []int

func lowbit(u int) int {
    return int(u & -u)
}
func (a Tree) Add(u ,c int) {
    // 这里有大坑，每次调用 
    // var n = len(a)
    for u = u+1;u<len(a);u+= lowbit(u) {
        a[u] += c
    }

}

func (a Tree) QueryCnt(u int) int {
    var ans int
    for u = u+1;u>0; u -= lowbit(u) {
        ans += a[u]
    }
    return ans
}

func set0(a[]int) {
    var n = len(a)
    for i:=0;i<n;i++ {
        a[i] = 0
    }
}
type StreamRank struct {
	a Tree
}

func Constructor() StreamRank {
    var tree = make([]int,50002)
	return StreamRank{Tree(tree) }
}

func (this *StreamRank) Track(x int) {
	this.a.Add(x,1)
}

func (this *StreamRank) GetRankOfNumber(x int) int {
	rank := this.a.QueryCnt(x)
	 
	return rank
}