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

home_king

有一未排序的序列{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对数值集合如何最优化处理。

devel

用两重循环。。但格式不对，请大家修改。。。


#!/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";

libinary

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

home

最初由 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.我也不清楚。

home_king

最初由 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.集合是连续的。请看顶楼修改后的问题。

georgek

#!/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";

home_king

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

:cool:

libinary

“C的“快速排序”是稳定的。也就是说，序列的相对位置不变。”
排序算法的“稳定”是指相同大小的项的相对位置不变，不同大小的项肯定要变，否则怎么排序？
比如序列里有3个25：
...25(1)...25(2)...25(3)...
排序以后3个25应该是相邻的，但是稳定的算法保证3个25的顺序和原序列一样：
...25(1)25(2)25(3)...
所以，要得到{1,200,0}这种结果就不能排序。

devel

昨天的脚本想错了，不好意思？这个脚本出答案了。但有错误出现，可能是脚本的格式不对。

#!/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

devel

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()真是好东东。