专栏首页Michael阿明学习之路程序员面试金典 - 面试题 10.10. 数字流的秩(map/树状数组)

程序员面试金典 - 面试题 10.10. 数字流的秩(map/树状数组)

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(log⁡n)O(\log n)O(logn)
  • 读取秩的时候,从前往后遍历加起来(小于等于x的)O(n)O(n)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(log⁡n)O(\log n)O(logn)
  • 插入数以后,需要更新所有的 map 的 value,时间复杂度 O(n)O(n)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(n^2)O(n2)

如何优化:请看树状数组,一次查询和修改时间复杂度均为 O(log⁡n)O(\log n)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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 第 28 场双周赛(505/2144,前23.6%)

    全国排名: 505 / 2144,23.6%;全球排名: 1944 / 8571,22.7%

    Michael阿明
  • LeetCode 223. 矩形面积

    Michael阿明
  • LeetCode 347. 前 K 个高频元素(哈希/优先队列)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/top-k-frequent-elements 著作...

    Michael阿明
  • BZOJ2754: [SCOI2012]喵星球上的点名(AC自动机)

    attack
  • POJ 刷题系列:1753. Flip Game

    POJ 刷题系列:1753. Flip Game 传送门:POJ 1753. Filp Game 题意: 一个4*4的矩阵,每一格要么是白色,要么是黑色。现在...

    用户1147447
  • 【Codeforces 723C】Polycarp at the Radio 贪心

    n个数,用最少的次数来改变数字,使得1到m出现的次数的最小值最大。输出最小值和改变次数以及改变后的数组。

    饶文津
  • MCU SPI屏也能跑这么炫酷的特效?来,移植起来秀一秀

    最近智能小车的项目还在加功能调试中,等后续调试完毕后更文。今天咱们就来分享一个在Github上看到的非常有意思的GUI开源项目。

    morixinguan
  • C++初始化

    Qt君
  • 程序员进阶之算法练习(三十五)LeetCode专场

    LeetCode上的题目是大公司面试常见的算法题,今天的目标是拿下5道算法题: 题目1是基于链表的大数加法,既考察基本数据结构的了解,又考察在处理加法过程中的...

    落影
  • 程序员进阶之算法练习(三十五)LeetCode专场

    LeetCode上的题目是大公司面试常见的算法题,今天的目标是拿下5道算法题: 题目1是基于链表的大数加法,既考察基本数据结构的了解,又考察在处理加法过程中的边...

    落影

扫码关注云+社区

领取腾讯云代金券