面试题 10.10. 数字流的秩
假设你正在读取一串整数。每隔一段时间，你希望能找出数字 x 的秩(小于或等于 x 的值的个数)。请实现数据结构和算法来支持这些操作，也就是说：
实现 track(int x) 方法，每读入一个数字都会调用该方法；
实现 getRankOfNumber(int x) 方法，返回小于或等于 x 的值的个数。
注意：本题相对原题稍作改动
示例:
输入: ["StreamRank", "getRankOfNumber", "track", "getRankOfNumber"] [[], [1], [0], [0]] 输出: [null,0,null,1]
提示：
x <= 50000track 和 getRankOfNumber 方法的调用次数均不超过 2000 次原站题解
golang 解法, 执行用时: 100 ms, 内存消耗: 6.7 MB, 提交时间: 2022-11-29 16:14:48
type StreamRank struct {
slice []int
}
func Constructor() StreamRank {
s := StreamRank {
slice : make([]int,0),
}
return s
}
func (this *StreamRank) Track(x int) {
this.slice = append(this.slice,x)
sort.Ints(this.slice)
}
func (this *StreamRank) GetRankOfNumber(x int) int {
start, end := 0, len(this.slice)-1
for start <= end {
mid := start+(end-start)/2
if this.slice[mid] > x {
end = mid-1
} else {
if mid == len(this.slice)-1 || this.slice[mid+1] > x {
return mid+1
}
start = mid+1
}
}
return 0
}
/**
* Your StreamRank object will be instantiated and called as such:
* obj := Constructor();
* obj.Track(x);
* param_2 := obj.GetRankOfNumber(x);
*/
golang 解法, 执行用时: 32 ms, 内存消耗: 6.6 MB, 提交时间: 2022-11-29 16:13:24
type StreamRank struct {
m map[int]int
}
func Constructor() StreamRank {
m:=map[int]int{}
return StreamRank{m:m}
}
func (this *StreamRank) Track(x int) {
this.m[x]++
}
func (this *StreamRank) GetRankOfNumber(x int) int {
ans:=0
for k,v:=range this.m{
if x>=k{
ans+=v
}
}
return ans
}
/**
* Your StreamRank object will be instantiated and called as such:
* obj := Constructor();
* obj.Track(x);
* param_2 := obj.GetRankOfNumber(x);
*/
python3 解法, 执行用时: 108 ms, 内存消耗: 16.9 MB, 提交时间: 2022-11-29 16:12:16
class BIT:
def __init__(self, size):
self.data = [0] * (size + 2)
@staticmethod
def __lowbit(x):
return x & (-x)
def update(self, index, delta):
while index < len(self.data):
self.data[index] += delta
index += self.__lowbit(index)
def query(self, index):
ret = 0
while index > 0:
ret += self.data[index]
index -= self.__lowbit(index)
return ret
class StreamRank:
def __init__(self):
self.data = BIT(50000)
def track(self, x: int) -> None:
self.data.update(x + 1, 1)
def getRankOfNumber(self, x: int) -> int:
return self.data.query(x + 1)
# Your StreamRank object will be instantiated and called as such:
# obj = StreamRank()
# obj.track(x)
# param_2 = obj.getRankOfNumber(x)
java 解法, 执行用时: 15 ms, 内存消耗: 42.1 MB, 提交时间: 2022-11-29 16:10:55
class StreamRank {
List<Integer> list;
public StreamRank() {
list = new ArrayList<>();
}
public void track(int x) {
// 找到第一个大于x的数字，之后添加到下标i之前
list.add(binarySearch(x), x);
}
public int getRankOfNumber(int x) {
return binarySearch(x);
}
private int binarySearch(int target){
int l = 0, r = list.size() - 1;
while(l <= r){
int m = l + (r - l) / 2;
if(list.get(m) <= target){
l = m + 1;
}else{
r = m - 1;
}
}
return l;
}
}
/**
* Your StreamRank object will be instantiated and called as such:
* StreamRank obj = new StreamRank();
* obj.track(x);
* int param_2 = obj.getRankOfNumber(x);
*/