面试题_数字流的秩

难度：中等

题目

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

解题

这道题比较灵活，可以有多种解法，最简单的就是粗暴解法用 int 数组存储数字，数组初始化大小为最大大小 50001，每个位置存储该位置的数字个数，track 的时候就向位置 ++，求秩则从 0 加到 x。 这个方法有局限性，就是限制了添加数字的最大值。

粗暴解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class StreamRank {
    public int[] list;
    public StreamRank() {
        list = new int[50001];
    }
    
    public void track(int x) {
        list[x]++;
    }
    
    public int getRankOfNumber(int x) {
        int ans = 0;
        for (int i=0;i<=x;i++){
            ans+=list[i];
        }
        return ans;
    }
}

二分法是效率比较高的方法，且不受添加数字大小限制，track 的时候先找到位置再添加，求秩即返回它的位置。与上面方法相比，添加比较麻烦，但是求秩效率很高。

二分法解法：

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
class StreamRank {
  List<Integer> list;

  public StreamRank() {
    list = new ArrayList<>();
  }

  public void track(int x) {
    // 找到第一个大于x的位置，插入x
    list.add(search(x), x);
  }

  public int getRankOfNumber(int x) {
    return search(x);
  }

  private int search(int x) {
    int l = 0, r = list.size() - 1;
    while (l <= r) {
      int mid = l + (r - l) / 2;
      if (list.get(mid) > x) r = mid - 1;
      else l = mid + 1;
    }
    return l;
  }
}