合并两个有序数组

合并两个有序数组。

 

题目2年前面baidu的时候问的，看起来很简单，写起来还是容易错。当年太菜，写的少。现在写出来不错也不容易。第二种解法写了很久，实际是相当复杂的。

 

最简单的当然是新建一个数组然后一个个往里面放。

其复杂度为a+b

 

 

Solution 1 :这个二分法插入是不额外开辟空间的，逐个插入。

复杂度大致为 b*log(a)

 

Solution 2 :从B中用二分法选取插入的连续元素块，直接插入数个元素

初始值x=0;

b[x]应插入到a[cur]的位置(二分法得到位置），那么直到b中最后一个小于a[cur+1]的元素b[y](二分法得到y)共y-x个，都应依次插入到当前a[cur]的位置，从a[cur+1]开始剩余的元素，都应向后移动y-x个位置。

完成后则b[y]之前的元素都已经插入。然后x置为y+1,重复以上操作，直至所有b中元素都插入a中

二分查找时对位置加以限制，从上轮插入结束的位置开始，这样又降低了部分复杂度

复杂度大致为log2(a)+log2(b). 最差时比较和移动了a+b次

 

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;
    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 ;

}

#! /usr/bin/perl
my @b = (2,4,6,8);
my @a = (1,3,5,7);

my $count = 0;

sub getInsertPostion{
    my ($in, $si, $ei, @queue) = @_;
    if($in<$queue[$si]){
        $count++;
        return $si;
    }
    if($in>=$queue[$ei]){
        $count++;
        return @queue;
    }
    my $cur;
    do{
        $cur = int(($si+$ei)/2);
        $ei = $cur if($in<=$queue[$cur]);
        $si = $cur if($in>=$queue[$cur]);
        $count ++;
    }
    while($ei-$si >1);
    return $ei;
}
my $asi = 0;
my $bsi = 0;
my $aei = @a-1;
my $bei = @b-1;
my $size = @a+@b;
while(@a<$size){
    #while instert elements of b into a at the postion $cur
    my $cur = getInsertPostion($b[$bsi], $asi, $aei, @a);
    my $bei = getInsertPostion($a[$cur], $bsi, $bei, @b);


    #the steps for @a to move forward
    my $steps = () = ($bsi..$bei);
    $steps --;
    print "Step = $steps \n";

    #move the elements of a after postion $cur by steps
    for(0..(@a-$cur-1)){
        $a[$aei-$_+$steps] = $a[$aei-$_];
    }
    print "after move foward by step $steps: @a \n";

    #insert elements selected from b
    #if steps is 0, it means that all left element of @b should append to @a.
    $bei = @b if($steps == 0);

    for($bsi..$bei-1){
        print "fill a[$cur] with $b[$_]\n";
        $a[$cur] = $b[$_];
        $cur++;

    }
    print "@a \n";

    #next round, select elements of b from the postion that ending this round
    $bsi = $bei;
    $bei = @b-1;

    #the next round will start from the postion after insert.
    $asi = $cur+ $steps;
    $aei = @a-1;
    print "--------------------------------------\n";
}

print "@a \n";
print "Compare executed for $count times\n";