网站建设开发设计营销公司山东,开发公司工程部年终总结,如何选择企业网站开发,机票旅游网站建设文章目录1. 题目2. 解题2.1 map2.2 树状数组1. 题目
假设你正在读取一串整数。每隔一段时间#xff0c;你希望能找出数字 x 的秩(小于或等于 x 的值的个数)。
请实现数据结构和算法来支持这些操作#xff0c;也就是说#xff1a; 实现 track(int x) 方法#xff0c;每读入…
文章目录1. 题目2. 解题2.1 map2.2 树状数组1. 题目
假设你正在读取一串整数。每隔一段时间你希望能找出数字 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 次来源力扣LeetCode 链接https://leetcode-cn.com/problems/rank-from-stream-lcci 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
类似题目LeetCode 315. 计算右侧小于当前元素的个数二叉查找树二分查找归并排序逆序数总结
2.1 map
map 存储自己的个数写入时间复杂度 O(logn)O(\log n)O(logn)读取秩的时候从前往后遍历加起来小于等于x的O(n)O(n)O(n) 时间复杂度
class StreamRank {mapint,int m;int count 0;
public:StreamRank() {}void track(int x) {m[x];}int getRankOfNumber(int x) {count 0;for(auto mi : m){if(x mi.first)count mi.second;elsebreak;}return count;}
};108 ms 13.9 MB
map 存储前面小于等于它的个数读取秩的时间复杂度 O(logn)O(\log n)O(logn)插入数以后需要更新所有的 map 的 value时间复杂度 O(n)O(n)O(n)
class StreamRank {mapint,int m;
public:StreamRank() {}void track(int x) {auto it m.rbegin();for(; it ! m.rend(); it){if(it-first x)it-second;//有比x大的他们的value比它小的个数 1elsebreak;}if(it m.rend() || (it ! m.rend() it-first x))m[x]; // map遍历到头了x不存在或者x存在elsem[x] it-second 1;//遍历没到头x不存在x 的 value 前一个value 自己}int getRankOfNumber(int x) {if(m.empty() || x m.begin()-first)return 0;if(m.count(x))return m[x];auto end m.upper_bound(x);end--;return end-second;}
};120 ms 14 MB 2.2 树状数组
上面解法在 n 次操作下的时间复杂度为 O(n2)O(n^2)O(n2)
如何优化请看树状数组一次查询和修改时间复杂度均为 O(logn)O(\log n)O(logn)
class StreamRank {vectorint v;int N 50002;
public:StreamRank() {v vectorint(N);}void track(int x) {update(x1, 1);}int getRankOfNumber(int x) {return query(x1);}//-----树状数组-------int lowbit(int x){return x(-x);}void update(int i, int delta){for( ; i N; i lowbit(i))v[i] delta;}int query(int i){int sum 0;for( ; i 0; i - lowbit(i))sum v[i];return sum;}
};44 ms 20.6 MB
