待字闺中之又见Google之星分析

题目来源，待字闺中，原创@陈利人 ，欢迎大家继续关注微信公众账号“待字闺中”

原题

给定一批查询日志，数量为n。其中，有的查询出现了多于n/3次，请在线性时间内，找到所有满足条件的查询。

分析

如果初次遇到这个问题，我们会有什么样的思路呢？

1. 采用hashmap进行计数，O(n)的空间，O(n)的时间
2. 进行排序，O(nlogn)
3. 快速选择算法，这个也可以做到O(n)的时间。

但是，如果面试官进一步限制了可以采用方法的范围：不允许使用上述方法，该如何处理呢？

我们在之前的面试题目中，遇到过类似的一个问题：那次的查询出现的次数是一半以上。大家还记得，我们的解法么？道理很简单，但解法是很巧妙的，当我们每次去掉两个不相同的查询，那最终剩下的查询，就是我们要找的查询——这个查询的出现次数，占了一半以上。

那如果是多于n/3次呢？更一般的情况下，如果是多于n/m次呢？道理完全一样的：我们每次去掉m个不同的查询，那最终剩下的查询，就是我们要找的备选的。道理很简单，可是要如何实现呢？之前的题目，是比较简单就能够实现每次去掉两个不同的查询的，更一般的情况下，如何每次去掉m个不同的元素呢？

下面我们会介绍一种实现方法，核心的原理就是：每次去掉m个不同的查询。第一个方法，是很有趣的一个方法，相信能够给大家以启发。

一种有趣的实现

有一个经典的游戏，叫做俄罗斯方块。想必很多同学都玩过的吧，俄罗斯方块，有不同颜色、不同形状的方块，从上往下落，如果砌满一行，这一行就会消失。一般列数都是固定的，在玩儿的过程中不会变化。这里要讲的一个实现，就是从俄罗斯方块这个游戏启发而来的。

我们申请一个大小为m的map，开始遍历查询日志，如果：

1. 遇到一个不在map中的查询，则插入map中，并且将值设置为1（相当于新落下一个方块）
2. 遇到一个在map中的查询，则将map中，该查询对应的值加1（相当于在已有的方块上又多加了一个）

当map中的查询个数等于m时，则对map中所有查询的值减一（相当于砌满了一层，就会消掉）。直到遍历完毕查询日志，map中还存在的查询，就是我们要找的查询的备选。我们看下面的具体的例子：

查询日志为：4 3 3 2 1 2 3 4 4 7 且m=5

上述方法的步骤如下：

当 4 3 3 落入到map中的时候，map的形状如下：

当 2 1 2 3 落入到map中的时候，map形状如下：

当 4 4 落入到map中的时候，map的形状如下：

当 7 落入到map中的时候，map形状如下：

此时，map的大小=5，可以消除一行了。

消除之后如下图：

此时剩下三个查询，但不都是满足条件的查询，需要逐个验证。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之星分析,布布扣,bubuko.com

待字闺中之又见Google之星分析

原文：http://blog.csdn.net/fangjian1204/article/details/37880845