技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 算法 --> 腾讯-1亿个数据取前1万大的整数-题解答

腾讯-1亿个数据取前1万大的整数-题解答

浏览:8900次  出处信息

    题目描述:

    1亿个数据取前1万大的整数

    常规思路:

    运用数据结构里面描述的常规排序算法,快速排序法是常规排序中速度最快的

    我的思路:

    ====我的机器太差,就不跑1亿数据了,10000吧

    1、把1亿个数据分成10000个数组,

    2、求出10000个数组的最大值,保存到$max 数组中,

    3、对$max本身用快速排序法排序 $max数组中保存了一个有序序列数组

    4、遍历1亿个数据,依次对比$max从大到小的数据,如果比max数组中的数据大,就替换。

    5、获得10000个从大到小的数据$max.

    代码:

以下是代码片段:
< ?php
 
/**
 * 交换两个数据的值
 *
 * @param unknown_type $x
 * @param unknown_type $y
 */
function swap(&$x,&$y)
{
    $c = $x;
    $x = $y;
    $y = $c;    
}
 
/**
 * 快速排序函数
 *
 */
function quicksort( $arr, $l = 0 , $r = NULL ) {
    static $list = array();
    if( $r == NULL )
        $list = $arr;
 
    if( $r == NULL )
        $r = count($list)-1;
 
    $i = $l;
    $j = $r;
 
    $tmp = $list[(int)( ($l+$r)/2 )];
    do {
        while( $list[$i] < $tmp )
            $i++;
 
        while( $tmp < $list[$j] )
            $j--;
 
        if( $i <= $j ) 
        {
           swap($list[$i],$list[$j]);
           $i++;
           $j--;
        }
    }while( $i <= $j );
 
    if( $l < $j )
        quicksort(NULL, $l, $j);
 
    if( $i < $r )
        quicksort(NULL, $i, $r);
 
    return $list;
}
 
/**
 * 计算运行时间类
 *
 */
class timer 

    var $StartTime = 0; 
    var $StopTime = 0; 
    var $TimeSpent = 0; 
    function start()
    { 
      $this->StartTime = microtime(); 
    } 
    function stop()
    { 
      $this->StopTime = microtime(); 
    } 
    function spent() 
    { 
      if ($this->TimeSpent)
      { 
               return $this->TimeSpent; 
      }
      else
      { 
           $StartMicro = substr($this->StartTime,0,10); 
           $StartSecond = substr($this->StartTime,11,10); 
           $StopMicro = substr($this->StopTime,0,10); 
           $StopSecond = substr($this->StopTime,11,10); 
           $start = doubleval($StartMicro) + $StartSecond; 
           $stop = doubleval($StopMicro) + $StopSecond; 
           $this->TimeSpent = $stop - $start; 
           return substr($this->TimeSpent,0,8)."秒"; 
      } 
    }
}//end class timer;
 
//构造1000000个数据的数组
// $number 拆分1000*1000数组
// $number2 1000000个数据的1维数组
 
for($i=0;$i< = 999;$i++)
{
    for($j=0;$j<=999;$j++)
    {
        $number2[] = $number[$i][$j] = rand(0,10000);
    }
}
 
$timer = new timer; 
$timer->start(); 
 
$max = array();
foreach ($number as $list)
{
    $maxvalue = 0;
    foreach ($list as $value)
    {
        if($maxvalue < $value)
        {
            $maxvalue = $value;
        }
    }
    $max[] = $maxvalue;
}
 
 
$max = quicksort($max,0);
for($i=0;$i < 1000000;$i++)
{
        //如果数组的数据大于max最小值,则从大到小对比其他数据
    if($number2[$i] >$max[0])
    {
        for ($k=999;$k>=0;$k--)
        {
            if($max[$k] < $number2[$i])
            {
                    //替换数据
                $max[$k] = $number2[$i];
                break;
            }
        }
    }
}
 
$timer->stop(); 
 
echo ’第一次排序时间:’.$timer->spent();
/*print_r($max);*/
$timer2 = new timer();
$timer2->start();
quicksort($number2,0);
$timer2->stop();
echo ’第2次排序时间:’.$timer2->spent();
/*print_r($number2);*/

    运行结果:

    第一次排序时间:2.370435秒

    第2次排序时间:38.43304秒

    ps:

    运行时间可能有所变化,我是在几年前的笔记本上,ZEND测试的,不过显然第一次排序结果速度更快

建议继续学习:

  1. 如何使用1M的内存排序100万个8位数    (阅读:10653)
  2. 快速排序(Quicksort)的Javascript实现    (阅读:9923)
  3. 谷歌(Google)2011年校园招聘笔试题    (阅读:8848)
  4. 你是那10%可以实现二分查找算法的程序员吗?    (阅读:6406)
  5. 深入浅出插入类排序算法(直接插入, 折半插入, 希尔排序)    (阅读:6018)
  6. 深入浅出交换类排序算法(冒泡排序,快速排序)    (阅读:5812)
  7. 15道使用频率极高的基础算法题    (阅读:5386)
  8. 新浪微博笔试题:找出共有2个以上标签的用户对    (阅读:4827)
  9. 有道实习生笔试总结    (阅读:4489)
  10. Java程序员必知的8大排序算法    (阅读:4253)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1