LeetCode 面试题 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 次

  点击此处跳转题目。

二、C# 题解

  使用数组存储加入的 x，并计算 x 的秩。为了便于计算秩，需要将数组升序排列。因此，插入和查找时都必须保持升序的顺序，可以使用二分进行操作：

public class StreamRank {
    private class Data
    {
        public int x;    // 值
        public int rank; // x 的秩
    }

    private List<Data> datas; // 存储 Data，以 x 的值升序排列

    public StreamRank() {
        datas = new List<Data>();
    }

    public void Track(int x) {
        if (!Find(x, out int i)) {                           // 如果没找到 x
            int num = i > 0 ? datas[i - 1].rank : 0;         // 获取前一个位置的 rank
            datas.Insert(i, new Data { x = x, rank = num }); // 在 i 处插入 x
        }
        for (int j = i; j < datas.Count; j++) datas[j].rank++; // 更新大于 x 的数的秩
    }

    public int GetRankOfNumber(int x) {
        if (Find(x, out int i)) return datas[i].rank; // 找到有 x，直接返回 x 的秩
        return i > 0 ? datas[i - 1].rank : 0;         // 未找到，则返回前一个数的秩
    }

    // 在 datas 中二分查找 x，返回是否找到，下标存储在 index 中
    // 若未找到，则 index 被设置为 x 按升序应插入的位置
    private bool Find(int x, out int index) {
        int i = 0, j = datas.Count;
        while (i < j) {
            int mid = (i + j) / 2;
            if (x == datas[mid].x) {
                index = mid;
                return true;
            }
            if (x > datas[mid].x) i = mid + 1;
            else j = mid;
        }
        index = i;
        return false;
    }
}

/**
 * Your StreamRank object will be instantiated and called as such:
 * StreamRank obj = new StreamRank();
 * obj.Track(x);
 * int param_2 = obj.GetRankOfNumber(x);
 */
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
47
48
49
50

• 时间：108 ms，击败 100.00% 使用 C# 的用户
• 内存：50.35 MB，击败 100.00% 使用 C# 的用户