php大数组交集处理


在针对用户信息处理过程中遇到这样一个问题.将基于用户的某项信息分别存于两个大数组(用于用户数据合并).预计量级均在10万级. 数据结构如下:

   
  $area1 = array(
  
'test1'=>'level1',
'test2'=>'levle2',
'test3'=>'levle3',
'test4'=>'level4'
);

$area2 = array(
'test1'=>'level1',
'test2'=>'level1',
'test5'=>'level1',
'test6'=>'level1'
);

如上,两个数组中分别保存有用户数据.要求针对两数组进行如下处理.
1.找出key相同的元素(即用户名相同).
2.将相同的key以别名的方式(如上,test1,test2为冲突key.要求将其找出然后改为test11, test12; test21 test22;)进行保存.
3.合并两个数组.最终得到的应该是

   
  $area_merge = array(
  
'test11'=>'level1',
'test12'=>'level1',
'test21'=>'levle2',
'test22'=>'levle1',
'test3'=>'levle3',
'test4'=>'level4'
'test5'=>'level1',
'test6'=>'level1'
).

原则上按照以上思路,可以通过key的求交,获得交集数组,然后再分别处理原始两个数组.遍历查找.这样的时间复杂度应该是O(n^2).不知各位有没有更好的方案来进行优化.欢迎赐教 @冯义军

php 算法

Amazing 11 years, 8 months ago

如果把两个数组先排序再归并, 时间复杂度应该是O(n*lg(n));

但是我记得php中关联数组其实就是 hash, 按key查找时间复杂度应该是O(1); 那么我们设数组为arr1, arr2; copy arr2到数组arr3; 遍历arr1, 按key去arr3中查找, 重复按你的方法处理,不重复加入arr3中; 返回arr3为结果数组. 时间复杂度应该是O(n).
本人对php仅是入门, 欢迎指正, 共同进步.

终于注册成功了 answered 11 years, 8 months ago

Your Answer