首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

请问大牛们一个有关问题

2012-02-25 
请教大牛们一个问题!情况是这样的:从1-33中任选6个数字(无放回),并对其进行排序后,组成一个数组,记为a。现

请教大牛们一个问题!

情况是这样的:
从1-33中任选6个数字(无放回),并对其进行排序后,组成一个数组,记为a。
现有两个大集合
A:a1,a2,...,aM
B:b1,b2,...,bN
M,N都很大,通常M有10来万,N有30多万。

现在要针对A中的每一个数组ai,统计b1,...,bN中有多少个与ai有5个元素相同。

我现在的做法就是就是先写一个比较两个数组有几个元素相同的函数,简记为find(a,b),
a,b为数组,返回相同元素的个数,然后简单的循环遍历。

for i:=0 to M-1 do
  for j:=0 to N-1 do
  if find(ai,bj)=5 then count[i]:=count[i]+1;

这算起来特别慢,不知道有没有好的方法来提高一下性能,谢谢了。


[解决办法]
如果是所有元素相同的话,排序(nlogn)以后扫描一下就完了。当然对logn不爽的话可以用hashtable。

现在是5个元素,所以枚举6*6个不必考虑的那个位置,然后套用上面的排序(或hash)+扫描。
[解决办法]
B中的每个数组生成HASH吧,1个变6个,最多30*6万个HASH元素。
这样对于每一个ai时间复杂度为6。
这个循环的总时间复杂度大概为O(6N+6M)。

另外每个这个数组完全可以用一个int32型的整数保存,既省空间又提高运行效率。

热点排行