文档章节

待字闺中:日志查询。(网络摘要)

昏鸦
 昏鸦
发布于 2014/03/02 10:10
字数 290
阅读 39
收藏 0

给定一批查询日志,数量是n,有的查询条件出现了 n/m 次。找出这些次数

1: 采用hashmap 经行计数,,O(N) 的空间,O(n) 的时间

2: 进行排序,O(nlogn)

3: 快速排序,也可以做到O(n)

4:我们申请一个大小为M的map,开始变量查询日志,如果:

      遇到一个不在map中的查询,则插入map,并且将值设置为1,遇到一个在map中的查询,则将map该查询对应的值加1

      当map的查询个数等于m时,则对map中所有查询的值减一,

例子:

        查询日志:4 3 3 2 1 2 3 4 4 7 且m是5

当 4 3 3 落入map中的时候,map的形状如:   

                         3

      4                 3

          

当 2 1 2 3 落入map中的时候,map形状如:

                          3

                          3                                       2

       4                 3                    1                 2  

当 4 4 落入map的时候

                        3

       4               3                                       2

       4               3                    1                 2             7

此事map的大小=5,可以消除一行

              3

4             3          2

此时剩下三个查询

基于数的,整个时间复杂度是o(n logm)








© 著作权归作者所有

共有 人打赏支持
昏鸦
粉丝 7
博文 182
码字总数 59043
作品 0
程序员
私信 提问
面试题:搜索大于n/3个数的变量

感谢陈立人http://weibo.com/lirenchen?topnav=1&wvr=5&topsug=1的每天一道面试题的资料整理。关注“待字闺中”的微信,里面有题目的分析。我会post他整理的题目,供大家一起学习。 原题 给定...

陈凯俊
2013/08/05
0
2
基于深度学习的分词系统--kcws

这是一个基于深度学习的分词系统和语料项目。 背景 97.5%准确率的深度学习中文分词(字嵌入+Bi-LSTM+CRF) 构建 安装好bazel代码构建工具,clone下来tensorflow项目代码,配置好(./configur...

koth
2016/11/25
7.6K
1
灯;及数组统计分析

今日面试题:灯 有100盏灯,依次编号1-100,初始都是关着的。第1次遍历,打开全部的灯;第2次遍历,关掉第2盏、第4盏等被2整除的灯;第3次打开被3整除的灯;第i次,对被i整除的灯做如下操作 ...

不最醉不龟归
2016/11/02
3
0
今年9岁的区块链,为何突然成为宠儿?

     虽不像人工智能一样经历几大起落,但区块链技术在2018年得到持续关注,是存在一些值得推敲的地方。那么区块链技术真正能够火起来,以太坊的出现,功不可没。   币:冰与火之歌  ...

乌镇智库
03/20
0
0
求一个数组中子数组的最大和算法(Java实现)

前几天在微信订阅号“待字闺中”中看到的一篇文章《小技巧求一个数组中子数组的最大和》,提供下Java的实现,并且在对题目做下小修改,本来打算直接在微信里直接回复,但是发现无法回复,然后...

囚兔
2016/07/03
89
0

没有更多内容

加载失败,请刷新页面

加载更多

开源软件会被云杀死吗 ?

本文转载云头条,原作者:Michael Stiefel是Reliable Software公司的负责人,是一名软件架构和开发顾问。 文章要点 虽然开源开发不会消失,但商业开源厂商的未来不是很有希望。随着全面管理的...

linuxCool
21分钟前
0
0
OSChina 周三乱弹 —— 谈什么对象?睡什么觉?

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @胖达panda :最肯忘却古人诗,最不屑一顾是相思。分享童丽的单曲《红豆生南国》: 《红豆生南国》- 童丽 手机党少年们想听歌,请使劲儿戳(这...

小小编辑
25分钟前
43
3
stylus

stylus基础教程,stylus实例教程,stylus语法总结

miaojiangmin
今天
3
0
PHP生成CSV之内部换行

当我们使用PHP将采集到的文件内容保存到csv文件时,往往需要将采集内容进行二次过滤处理才能得到需要的内容。比如网页中的换行符,空格符等等。 对于空格等处理起来都比较简单,这里我们单独...

豆花饭烧土豆
今天
2
0
使用 mjml 生成 thymeleaf 邮件框架模板

发邮件算是系统开发的一个基本需求了,不过搞邮件模板实在是件恶心事,估计搞过的同仁都有体会。 得支持多种客户端 支持响应式 疼彻心扉的 outlook 多数客户端只支持 inline 形式的 css 布局...

郁也风
今天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部