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)) {                           // 如果没找到 xint num = i > 0 ? datas[i - 1].rank : 0;         // 获取前一个位置的 rankdatas.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);*/

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