假设你正在读取一串整数。每隔一段时间，你希望能找出数字 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 次
解题思路
1，这是二分查找的拓展
2，包含二分查找和二分插入
3，与二分查找的区别是，找到mid位置后，如果mid位置的值<=target ,需要后移mid
代码实现
代码语言：javascript复制type StreamRank struct {
data []int
}
func Constructor() StreamRank {
return StreamRank{}
}
func (this *StreamRank) getMid(x int)int{
i:=0
j:=len(this.data)-1
mid:=(i j)/2
for i 1<j{
if this.data[mid]==x{
break
}
if this.data[mid]<x{
i=mid 1
}else{
j=mid-1
}
mid=(i j)/2
}
for mid <len(this.data) &&this.data[mid]<=x && mid<len(this.data){
mid
}
return mid
}
func (this *StreamRank) Track(x int) {
if len(this.data)==0{
this.data=append(this.data,x)
return
}
mid:=this.getMid(x)
d:=this.data[mid:]
this.data=append(this.data[:mid:mid],x)
this.data=append(this.data,d...)
return
}
func (this *StreamRank) GetRankOfNumber(x int) int {
if len(this.data)==0{
return 0
}
mid:=this.getMid(x)
return mid
}
/**
* Your StreamRank object will be instantiated and called as such:
* obj := Constructor();
* obj.Track(x);
* param_2 := obj.GetRankOfNumber(x);
*/
