LinuxSir.cn,穿越时空的Linuxsir!

 找回密码
 注册
搜索
热搜: shell linux mysql
查看: 1196|回复: 10

在一序列中删除某个范围的所有数

[复制链接]
发表于 2003-12-12 22:56:50 | 显示全部楼层 |阅读模式
有一未排序的序列{n1,n2,....nN},要求删除nk(k=1,2,...N),nk属于范围start至end的数。例如,序列{1,5,98,200,0,25},集合{4,5,6,...100}(m个连续数),删除操作结束后结果为{1,200,0}。
求一最优算法。

我用C实现的算法为:
1. 对该序列进行“快速排序”,时间复杂度为O(nln(n)/ln2),整理成“二叉排序树”( p->lchild->data > p->data > p->rchild )
2. 在二叉排序树上从100开始删除到4为止,每次比较的次数都不超过树的高度ln(n)/ln2,共比较m次。
总的时间复杂度为O(nln(n)/ln2)+O(mln(n)/ln2)。

应该最好啦。不知道Perl对数值集合如何最优化处理。
发表于 2003-12-12 23:42:00 | 显示全部楼层
用两重循环。。但格式不对,请大家修改。。。


#!/usr/bin/perl -w
@a=qw(1 2 3 4 5 6 7 8 9 0);
$loopa=@a;
print "@a\n$loopa\n";
@b=qw(2 4 5 7);
$loopb=@b;
print "@b\n$loopb\n";
for ($loopb;$loopb>=0;$loopb--) {
for($looa;$loopa>=0;$loopa--) {
if( @b[$loopb] =! @a[$loopa] ) {
unshift (@result,"$_");
}
}
}
@re=sort(@result);
print "@re\n";
发表于 2003-12-13 01:50:58 | 显示全部楼层

回复: 在一序列中删除某个范围的所有数

1、“删除操作结束后结果为{1,200,0}”
看这个结果原序列的相对位置是不变的,如果先排序的话结果就是{0,1,200},不知道这个符合题意不。
2、集合{4,5,6,...100}是不是连续的?如果是连续的就好办。
发表于 2003-12-13 02:03:33 | 显示全部楼层

回复: 回复: 在一序列中删除某个范围的所有数

最初由 libinary 发表
1、“删除操作结束后结果为{1,200,0}”
看这个结果原序列的相对位置是不变的,如果先排序的话结果就是{0,1,200},不知道这个符合题意不。
2、集合{4,5,6,...100}是不是连续的?如果是连续的就好办。


1.那就用unpop()不要sort()
这也是个错误的脚本,请大家修改。
#!/usr/bin/perl -w
@a=qw(1 2 3 4 5 6 7 8 9 0);
$loopa=@a;
@b=qw(2 5 6);
$loopb=@b;
for($loopb;$loopb>=0;$loopb--) {
   for($loopa;$loopa>=0;$loopa--) {
          if ($b[$loopb] != $a[$loopa] ) {
             unpop(@result,"$_");
             }
    }
}
print "@result\n";


2.我也不清楚。
 楼主| 发表于 2003-12-13 12:55:01 | 显示全部楼层

回复: 回复: 在一序列中删除某个范围的所有数

最初由 libinary 发表
1、“删除操作结束后结果为{1,200,0}”
看这个结果原序列的相对位置是不变的,如果先排序的话结果就是{0,1,200},不知道这个符合题意不。
2、集合{4,5,6,...100}是不是连续的?如果是连续的就好办。


1.C的“快速排序”是稳定的。也就是说,序列的相对位置不变。Perl如何实现快速排序呢?毕竟,双重循环的直接对比的时间复杂度搞不好就是O(n^2),而在排序算法中,时间复杂度理论上的最优下限为O(nln(n)/ln2),快速排序为其一,用于本题,更考虑到稳定性。Perl能否实现快速算法就成了关键,系统调用方面可作优化。
2.集合是连续的。请看顶楼修改后的问题。
发表于 2003-12-13 17:47:17 | 显示全部楼层
#!/usr/bin/perl -w
my @a=qw(1 2 3 4 5 6 7 8 9 0);
my $d=join("",@a);#去掉空格。
my @b=qw(2 5 6);
foreach my $c(@b){
$d =~ s/$c//;#把@a中有@b的删去。
}
print "$d\n";
 楼主| 发表于 2003-12-13 20:55:23 | 显示全部楼层

正则表达式处理这类问题就是漂亮。
(Perl模式匹配的效率应该挺高的,因为Perl的基本原则就是快嘛,是吧,呵呵:-)

:cool:
发表于 2003-12-13 23:09:57 | 显示全部楼层
“C的“快速排序”是稳定的。也就是说,序列的相对位置不变。”
排序算法的“稳定”是指相同大小的项的相对位置不变,不同大小的项肯定要变,否则怎么排序?
比如序列里有3个25:
...25(1)...25(2)...25(3)...
排序以后3个25应该是相邻的,但是稳定的算法保证3个25的顺序和原序列一样:
...25(1)25(2)25(3)...
所以,要得到{1,200,0}这种结果就不能排序。
发表于 2003-12-14 13:32:50 | 显示全部楼层
昨天的脚本想错了,不好意思?这个脚本出答案了。但有错误出现,可能是脚本的格式不对。
#!/usr/bin/perl -w
@a=qw(13 1 2 3 4 5 6 7 8 9 0 12 );
$loopa=@a;
@b=qw(2 5 6);
$loopb=@b;
for ( $i=0 ; $i < $loopa;$i++ ) {
    $flag=1;
LOOP1: for ( $j=0 ; $j < $loopb ; $j++ ) {
       if( @a[ $i ] == @b[ $j ] ) {
           $flag=0;
           last LOOP1 ;
        } }
     if ( $flag == 1) {
         push(@result, "@a[$i]" ) ;
      }
}
print "@result\n";

R# perl ok
Scalar value @a[ $i ] better written as $a[ $i ] at ok line 9.
Scalar value @b[ $j ] better written as $b[ $j ] at ok line 9.
Scalar value @a[$i] better written as $a[$i] at ok line 14.
13 1 3 4 7 8 9 0 12
发表于 2003-12-14 13:47:25 | 显示全部楼层
CU的麻辣兄的脚本:

#!/usr/bin/perl -w
@a=qw(12 1 3 6 8 7 78 2);
@b=qw(7 8);
foreach $a(@a) {
my $i=0;
foreach (@b) {
if ($_ eq $a) { $i=1; }
}
unless ( $i == 1 ) { @new_a=( @new_a , $a ); }
}
print "@new_a\n";

比我的简单多了,foreach()真是好东东。  
您需要登录后才可以回帖 登录 | 注册

本版积分规则

快速回复 返回顶部 返回列表