• 热门专题

Perl合并有序数组算法

作者:2B酱的编程Tips   发布日期:2012-06-19 09:13:20
Tag标签:合并有序数组  
  • 合并两个有序数组。
     
    题目2年前面baidu的时候问的,看起来很简单,写起来还是容易错。当年太菜,写的少。现在写出来不错也不容易。
    4最简单的当然是新建一个数组然后一个个往里面放。
    这个二分法插入是不额外开辟空间的。感觉复杂度还可以更低,但是弄起来会麻烦。再想想
    my @a = (1,3,5,7);
    my @b = (1,2,4,6,8);
    my $start = 0;
    my $end = @a -1 ;
    for my $t (@b){
        print "Tracking $t \n";
        my $cur;
        #binary search
        do{
            $cur = int(($start+$end)/2);
            $end = $cur if($t<$a[$cur]);
            $start = $cur if($t>$a[$cur]);
            if($t == $a[$cur]){
                $end = $cur +1;
                $start = $cur;
            }
        }
        while($end-$start >1);
        #assign the proper postion
        $cur = $end;
        #if the value is larger than the last element in current array, then append thelement to the last www.it165.net;
        if($t>$a[$end]){
            $cur = $end+1;
        }
        #move elements after current postion with distance 1
        for(my $i = @a-1; $i >= $cur; $i--){
            $a[$i+1] = $a[$i];
        }
        $a[$cur] = $t;
        $start = $cur;
        $end = @a-1;
        print "-----------@a---------------\n";
    }

延伸阅读:

About IT165 - 广告服务 - 隐私声明 - 版权申明 - 免责条款 - 网站地图 - 网友投稿 - 联系方式
本站内容来自于互联网,仅供用于网络技术学习,学习中请遵循相关法律法规