前41期一兄弟,去了趟百度,其中一道面试题是这样说,现在有10亿个url(有相同的),怎样统计数量最多的前十个,现在给出其中的一个解决方案,希望大家多提意见。
注意:我这里就不适用url,直接适用数字,原理都是一样的。
/**
*
@author:于燚:qq:496510819
*/
error_reporting(0);
$data_arr=array(1,2,3,4,2,1,3,3,3,3,4,5,64,5,3443,234,4,3545,3,2);
echo
"
不适用php的数组函数实现
";
class data_list{
public
$num;//当前数字
public $num_count=1;//保存当前的数字的个数
public
$pre_num=null;//保存上一个数字的引用
public $next_num=null;//保存下一个数字的引用
public
function
__construct($num=null){
$this->num=$num;
}
}
//创建一个头
$head=new
data_list();
foreach($data_arr as
$data){
//创建数字对象
$data_obj=new
data_list($data);
$current=$head;
while($current->next_num!=null){
if($current->num===$data_obj->num){
$current->num_count++;
$data_obj=null;
break;
}
$current=$current->next_num;
}
if($data_obj!==null){//表示当前没有这个数字还
$current->next_num=$data_obj;
$data_obj->pre_num=$current;
}else{//如果之前有这个数字则需要将这个节点往前移动
while($current->pre_num->pre_num!=null){
if($current->pre_num->num_count>=$current->num_count){//如果上一个节点的数量不少于当前节点则退出
break;
}
//移动节点
$current->next_num->pre_num=$current->pre_num;
$current->pre_num->next_num=$current->next_num;
$current->pre_num->pre_num->next_num=$current;
$current->next_num=$current->pre_num;
$current->pre_num=$current->pre_num->pre_num;
$current->next_num->pre_num=$current;
$current=$current->pre_num;
}
}
}
$c=$head;
while($c->next_num!=null){
echo
'数字:'.$c->next_num->num;
echo
'---数量为:'.$c->next_num->num_count.'
';
$c=$c->next_num;
}
原文地址:
阅读(308) | 评论(0) | 转发(0) |