程序员面试金典 - 面试题 10.10. 数字流的秩（map/树状数组）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了程序员面试金典 - 面试题 10.10. 数字流的秩（map/树状数组），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2350字，纯文字阅读大概需要4分钟。
内容图文
文章目录
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. 解题
2.1 map
- map 存储自己的个数，写入时间复杂度 O(logn)
- 读取秩的时候，从前往后遍历加起来（小于等于x的）O(n) 时间复杂度
class StreamRank {
map<int,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;
else
break;
}
return count;
}
};
108 ms 13.9 MB
- map 存储前面小于等于它的个数，读取秩的时间复杂度 O(logn)
- 插入数以后，需要更新所有的 map 的 value，时间复杂度 O(n)
class StreamRank {
map<int,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（比它小的个数） +1
else
break;
}
if(it == m.rend() || (it != m.rend() && it->first == x))
m[x]++; // map遍历到头了，x不存在，或者x存在
else
m[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(logn)
class StreamRank {
vector<int> v;
int N = 50002;
public:
StreamRank() {
v = vector<int>(N);
}
void track(int x) {
update(x+1, 1);
}
int getRankOfNumber(int x) {
return query(x+1);
}
//-----树状数组-------
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
内容总结
以上是互联网集市为您收集整理的程序员面试金典 - 面试题 10.10. 数字流的秩（map/树状数组）全部内容，希望文章能够帮你解决程序员面试金典 - 面试题 10.10. 数字流的秩（map/树状数组）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。