面试题 10.10. 数字流的秩

假设你正在读取一串整数。每隔一段时间，你希望能找出数字 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 次

Python 解答：
1.线性搜索

class StreamRank:

    def __init__(self):
        self.arr = []

    def track(self, x: int) -> None:
        if not self.arr:
            self.arr.append([x, 1])
        else:
            i = 0
            while i < len(self.arr):
                if self.arr[i][0] < x:
                    i += 1
                elif self.arr[i][0] == x:
                    for j in range(i, len(self.arr)):
                        self.arr[j][1] += 1
                    break
                elif self.arr[i][0] > x:
                    if i == 0:
                        self.arr.insert(i, [x, 1])
                    elif i > 0:
                        self.arr.insert(i, [x, self.arr[i-1][1]+1])
                    for j in range(i+1, len(self.arr)):
                        self.arr[j][1] += 1
                    break
            if i == len(self.arr):
                self.arr.append([x, self.arr[i-1][1]+1])

    def getRankOfNumber(self, x: int) -> int:
        i = 0
        while i < len(self.arr) and self.arr[i][0] <= x:
            i += 1
        if i - 1 < 0:
            return 0
        else:
            return self.arr[i-1][1]

# Your StreamRank object will be instantiated and called as such:
# obj = StreamRank()
# obj.track(x)
# param_2 = obj.getRankOfNumber(x)

2.树状数组

class StreamRank:

    def __init__(self):
        self.arr = [0 for i in range(50002)]

    def track(self, x: int) -> None:
        i = x+1
        while i < len(self.arr):
            self.arr[i] += 1
            i += i & (-i)

    def getRankOfNumber(self, x: int) -> int:
        total = 0
        i = x+1
        while i > 0:
            total += self.arr[i]
            i -= i & (-i)
        return total

# Your StreamRank object will be instantiated and called as such:
# obj = StreamRank()
# obj.track(x)
# param_2 = obj.getRankOfNumber(x)