网站制作郑州网站制作,专业seo站长工具,图片链接生成器在线制作,专业建站文章目录 一、题目二、C# 题解 一、题目 假设你正在读取一串整数。每隔一段时间#xff0c;你希望能找出数字 x 的秩(小于或等于 x 的值的个数)。请实现数据结构和算法来支持这些操作#xff0c;也就是说#xff1a; 实现 track(int x) 方法#xff0c;每读入一个数字都会调… 文章目录 一、题目二、C# 题解 一、题目 假设你正在读取一串整数。每隔一段时间你希望能找出数字 x 的秩(小于或等于 x 的值的个数)。请实现数据结构和算法来支持这些操作也就是说 实现 track(int x) 方法每读入一个数字都会调用该方法 实现 getRankOfNumber(int x) 方法返回小于或等于 x 的值的个数。
注意本题相对原题稍作改动
示例: 输入: [“StreamRank”, “getRankOfNumber”, “track”, “getRankOfNumber”] [[], [1], [0], [0]] 输出: [null,0,null,1] 提示
x 50000track 和 getRankOfNumber 方法的调用次数均不超过 2000 次 点击此处跳转题目。
二、C# 题解 使用数组存储加入的 x并计算 x 的秩。为了便于计算秩需要将数组升序排列。因此插入和查找时都必须保持升序的顺序可以使用二分进行操作
public class StreamRank {private class Data{public int x; // 值public int rank; // x 的秩}private ListData datas; // 存储 Data以 x 的值升序排列public StreamRank() {datas new ListData();}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# 的用户
