如何在大量的数据中判断一个数是否存在?
解答思路
方法一:分治法
依然可以用分治法解决,方法与前面类似,就不再次赘述了。
方法二:位图法
40 亿个不重复整数,我们用 40 亿个 bit 来表示,初始位均为 0,那么总共需要内存:4, 000, 000, 000b≈512M。
我们读取这 40 亿个整数,将对应的 bit 设置为 1。接着读取要查询的数,查看相应位是否为 1,如果为 1 表示存在,如果为 0 表示不存在。
方法总结
判断数字是否存在、判断数字是否重复的问题,位图法是一种非常高效的方法。
如何查询最热门的查询串?
题目描述
搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来,每个查询串的长度不超过 255 字节。
假设目前有 1000w 个记录(这些查询串的重复度比较高,虽然总数是 1000w,但如果除去重复后,则不超过 300w 个)。请统计最热门的 10 个查询串,要求使用的内存不能超过 1G。(一
个查询串的重复度越高,说明查询它的用户越多,也就越热门。)
解答思路
每个查询串最长为 255B,1000w 个串需要占用约 2.55G 内存,因此,我们无法将所有字符串全部读入到内存中处理。
方法一:分治法
方法可行,但不是最好,下面介绍其他方法。
方法二:HashMap法
虽然字符串总数比较多,但去重后不超过 300w,因此,可以考虑把所有字符串及出现次数保存在一个 HashMap 中,所占用的空间为 300w*(255+4)≈777M(其中,4表示整数占用的4个字
节)。由此可见,1G 的内存空间完全够用。
思路如下:
首先,遍历字符串,若不在 map 中,直接存入 map,value 记为 1;若在 map 中,则把对应的 value 加 1,这一步时间复杂度 O(N)。
接着遍历 map,构建一个 10 个元素的小顶堆,若遍历到的字符串的出现次数大于堆顶字符串的出现次数,则进行替换,并将堆调整为小顶堆。
遍历结束后,堆中 10 个字符串就是出现次数最多的字符串。这一步时间复杂度 O(Nlog10)
。
方法三:前缀树法
方法二使用了 HashMap 来统计次数,当这些字符串有大量相同前缀时,可以考虑使用前缀树来统计字符串出现的次数,树的结点保存字符串出现次数,0 表示没有出现。
思路如下:
在遍历字符串时,在前缀树中查找,如果找到,则把结点中保存的字符串次数加 1,否则为这个字符串构建新结点,构建完成后把叶子结点中字符串的出现次数置为 1。
最后依然使用小顶堆来对字符串的出现次数进行排序。
方法总结
前缀树经常被用来统计字符串的出现次数。它的另外一个大的用途是字符串查找,判断是否有重复的字符串等。
如何统计不同电话号码的个数?
全站分卷索引 · 72 卷
- 1互联网 Java 工程师进阶知识完全扫盲
- 2为什么使用消息队列?
- 3如何保证消息队列的高可用?
- 4如何保证消息不被重复消费?
- 5如何保证消息的可靠性传输?
- 6如何保证消息的顺序性?
- 7如何解决消息队列的延时以及过期失效问题?
- 8如何设计一个消息队列?
- 9搜索引擎
- 10ES 的分布式架构原理是什么?
- 11ES 写入数据的工作原理是什么?
- 12ES 在数十亿级别数量下如何提高查询效率?
- 13ES 生产集群的部署架构是什么?
- 14缓存
- 15Redis 和 Memcached 有什么区别?
- 16Redis 都有哪些数据类型以及适用场景?
- 17Redis 的过期策略都有哪些?
- 18如何保证 Redis 高并发、高可用?
- 19Redis 主从架构是怎样的?
- 20Redis 的持久化有哪几种方式?
- 21Redis 如何基于哨兵集群实现高可用?
- 22Redis 集群模式的工作原理能说一下么?
- 23Redis 的雪崩、穿透和击穿,如何应对?
- 24如何保证缓存与数据库双写一致性?
- 25如何解决 Redis 的并发竞争问题?
- 26生产环境中的 Redis 是怎么部署的?
- 27分库分表如何平滑过渡?
- 28设计一个动态扩容缩容的分库分表方案?
- 29分库分表之后,id 主键如何处理?
- 30读写分离
- 31高并发系统
- 32分布式系统
- 33系统拆分
- 34分布式服务框架
- 35Dubbo 支持哪些序列化协议?
- 36Dubbo 负载均衡策略和集群容错策略?
- 37Dubbo 的 SPI 思想是什么?
- 38如何基于 Dubbo 进行服务治理?
- 39分布式服务接口的幂等性如何设计?
- 40分布式服务接口请求的顺序性如何保证?
- 41如何自己设计一个类似 Dubbo 的 RPC 框架?
- 42CAP 定理的 P 是什么?
- 43分布式锁
- 44分布式锁如何设计?
- 45分布式事务
- 46分布式会话
- 47高可用架构
- 48电商网站详情页系统架构
- 49Hystrix 线程池技术实现资源隔离
- 50Hystrix 信号量机制实现资源隔离
- 51Hystrix 隔离策略细粒度控制
- 52深入 Hystrix 执行时内部原理
- 53基于 request cache 请求缓存技术优化批量商品数据查询接口
- 54基于本地缓存的 fallback 降级机制
- 55深入 Hystrix 断路器执行原理
- 56深入 Hystrix 线程池隔离与接口限流
- 57基于 timeout 机制为服务接口调用超时提供安全保护
- 58限流
- 59熔断
- 60微服务架构
- 61从单体式架构迁移到微服务架构
- 62微服务的事件驱动数据管理
- 63选择微服务部署策略
- 64Spring Cloud微服务架构
- 65你所知道的微服务技术栈都有哪些?
- 66谈谈服务发现组件 Eureka 的主要调用过程?
- 67海量数据处理
- 68如何找出某一天访问百度网站最多的 IP?
- 69如何在大量的数据中找出不重复的整数?
- 70如何在大量的数据中判断一个数是否存在?
- 71如何统计不同电话号码的个数?
- 72如何按照 query 的频度排序?