合并两个有序数组。
题目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";
}
RSS
