首页 > 代码库 > 待字闺中之又见Google之星分析
待字闺中之又见Google之星分析
题目来源,待字闺中,原创@陈利人 ,欢迎大家继续关注微信公众账号“待字闺中”
原题
给定一批查询日志。数量为n。
当中,有的查询出现了多于n/3次,请在线性时间内,找到全部满足条件的查询。
分析
假设初次遇到这个问题,我们会有什么样的思路呢?
- 採用hashmap进行计数,O(n)的空间,O(n)的时间
- 进行排序。O(nlogn)
- 高速选择算法。这个也能够做到O(n)的时间。
可是,假设面试官进一步限制了能够採用方法的范围:不同意使用上述方法。该怎样处理呢?
我们在之前的面试题目中,遇到过类似的一个问题:那次的查询出现的次数是一半以上。
大家还记得,我们的解法么?道理非常easy。但解法是非常巧妙的,当我们每次去掉两个不同样的查询,那终于剩下的查询。就是我们要找的查询——这个查询的出现次数,占了一半以上。
那假设是多于n/3次呢?更一般的情况下。假设是多于n/m次呢?道理全然一样的:我们每次去掉m个不同的查询。那终于剩下的查询,就是我们要找的备选的。道理非常easy,但是要怎样实现呢?之前的题目,是比較简单就行实现每次去掉两个不同的查询的,更一般的情况下,怎样每次去掉m个不同的元素呢?
以下我们会介绍一种实现方法,核心的原理就是:每次去掉m个不同的查询。
第一个方法。是非常有趣的一个方法。相信可以给大家以启示。
一种有趣的实现
有一个经典的游戏。叫做俄罗斯方块。
想必非常多同学都玩过的吧,俄罗斯方块,有不同颜色、不同形状的方块,从上往下落,假设砌满一行,这一行就会消失。一般列数都是固定的,在玩儿的过程中不会变化。这里要讲的一个实现,就是从俄罗斯方块这个游戏启示而来的。
我们申请一个大小为m的map,開始遍历查询日志,假设:
- 遇到一个不在map中的查询,则插入map中。而且将值设置为1(相当于新落下一个方块)
- 遇到一个在map中的查询。则将map中,该查询相应的值加1(相当于在已有的方块上又多加了一个)
当map中的查询个数等于m时,则对map中全部查询的值减一(相当于砌满了一层,就会消掉)。直到遍历完成查询日志。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中的时候。map的形状例如以下:
4 | 3 | ||
4 | 3 | 2 | |
4 | 3 | 1 | 2 |
当 7 落入到map中的时候。map形状例如以下:
4 | 3 | |||
4 | 3 | 2 | ||
4 | 3 | 1 | 2 | 7 |
此时。map的大小=5,能够消除一行了。
消除之后例如以下图:
4 | 3 | |||
4 | 3 | 2 |
此时剩下三个查询,但不都是满足条件的查询,须要逐个验证。O(n)就可以。
分析上述方法的空间复杂度为O(m).当m=3时,就能够觉得是常数空间。那么时间复杂度呢?切要看map是怎样实现的,假设是基于树的,整个的时间复杂度O(nlogm),m=3时,能够觉得是O(n)的。
代码例如以下:
void deleteOneLevel(map<int,int>& hashMap)//删除一层,就是每次删除m个元素 { map<int,int>::iterator iter1 = hashMap.begin(),iter2; while(iter1 != hashMap.end()) { (iter1->second)--; iter2 = iter1++; if(iter2->second == 0) { hashMap.erase(iter2->first); } } } bool check(vector<int>& data,int value,int length,int m)//检查hash表中剩余的元素是否符合要求 { int count = 0,i; for(i=0;i<length;i++) { if(data[i] == value)count++; if(count * m > length)return true; } return false; } vector<int> googleStar(vector<int>& data,int m) { int length = data.size(),i,j; vector<int> res; map<int,int> hashMap; for(i=0;i<length;i++) { hashMap[data[i]] ++; if(hashMap.size() == m)//hash表中有m种元素时,把每种元素减一,删除仅仅出现一次的元素 { deleteOneLevel(hashMap); } } map<int,int>::iterator iter = hashMap.begin(); while(iter != hashMap.end()) { if(check(data,iter->first,length,m))res.push_back(iter->first); iter ++; } return res; }
待字闺中之又见Google之星分析