LinuxSir.cn,穿越时空的Linuxsir!

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

去除数组中重复的冗余值

[复制链接]
发表于 2003-12-12 14:17:07 | 显示全部楼层 |阅读模式
去除一数组中重复的冗余值,如abbcbde-->abcde,要求时间复杂度及辅助空间复杂度平衡性最好的算法。
分析可知,时间复杂度取决于比较次数C与移动次数M。
两种方案:
方案一.顺序对比法
  1. i=1,j=n;                //i向后遍历,j向前遍历
  2. while(i<n)
  3. {
  4.         while (j>i)
  5.         {
  6.                 if (R[i]==-1 || R[j]==-1) break;
  7.                 if (R[j]==R[i]) R[j]=-1;                 //重值的冗余值都赋值为-1
  8.                 j--;
  9.         }
  10.         i++;
  11.         j=n;
  12. }
复制代码
可得C1(n)
//abbcbde变为a b -1 c -1 d e
//调整数组使之为abcde,略。可得M1(n)
O=C1(n)+M1(n)
辅助空间复杂度为O(0)

方案二.构造一游标数组,把数组“转换”为静态链表,此方案可省去移动调整步骤,但辅助空间复杂度为O(n)
  1. R[n]                Cursors[n]
  2. a                        0  <-head
  3. b                        1       
  4. b                        2       
  5. c                        3
  6. b                        4
  7. d                        5
  8. e                        6
  9. ...                        ...
  10. R[n-1]                NULL <-sq
  11. 以Cursors索引R,每次比较只调整Cursors。
复制代码
可见难以两全其美,兄弟们有更好的算法,不妨指点。
发表于 2003-12-12 20:12:56 | 显示全部楼层
这是CU release兄提供的方法,但unpop()过不了关?

#!/usr/bin/perl -w
use strict;

my @a=('a','b','b','b','c','d') ;
my $t=@a[0];
foreach (@a) {
if ($t==$_) { }
else {
unpop(my @b,$_);
$t=$_;
}
}
my @re=sort(@b);
print "@re\n";
发表于 2003-12-12 20:25:44 | 显示全部楼层
有漏洞, 这样会好些。

#!/usr/bin/perl -w
@a=('a','b','b','b','c','d') ;
$t=@a;
foreach (@a) {
if ( $t =! $_ ) {
unpop(@b,$_);
$t=$_;
}
}
if ( @re =! NULL ) {
@re=sort(@b);
}else {
@re=@a; }
print "@re\n";
 楼主| 发表于 2003-12-12 22:16:18 | 显示全部楼层

Perfect!

Perl处理字符串就是有一手!如此精简,复杂度和C的实现也差不多。
看来,C的索引在Perl里应换成pop操作最合适。
发表于 2003-12-12 22:49:57 | 显示全部楼层
请home_king兄把源码写写出来吧?那个unpop不懂得怎么用?
 楼主| 发表于 2003-12-13 13:09:08 | 显示全部楼层

unpop是什么,是push吗

呵呵,home兄,我对Perl懂得不多,严格来说还未入门。(还是那句话,课业太繁重啦,有空得想你和其他兄弟请教Perl:-)
之所以列出几道算法供兄弟们参考,一是有感Perl语言的高度精炼而又富有创意的表达力,在C领域里能实现的算法,到了这片神秘而又令众多黑客狂热的Perl世界里,是如何描述的呢?我很好奇,也有一种期待;二是欲一窥Perl的效率。
见笑。
要是C源码,我可以给出完整的求精程序。
发表于 2003-12-13 14:02:32 | 显示全部楼层
多谢home_king兄的提醒,我也是基础不好阿,学了就忘了些。这是正确的脚本:

#!/usr/bin/perl -w
@a=('a','b','b','b','c','d') ;
($t)=@a;
print "@a \n";
foreach (@a) {
if ( $t ne $_ ) {
push(@b , $_ ) ;
$t = $_;
} }
if ( @re ne NULL ) {
@b=(@b,$a[0]);
@re=sort(@b);
}else {
(@re)=@a; }
print "@re\n";
发表于 2003-12-13 20:47:07 | 显示全部楼层
CU的 gunguymadman007兄的脚本也不错。

#!/usr/bin/perl
@frist=(1,2,3,4);@second=(2,3,4,5);
for (@frist){$data{$_}=0;}
for (@second){$data{$_}=0;}
@thrid=sort {$a<=>$b} keys %data;
print "\@frist is @frist\t\t \@second is @second \t\t \@thrid is @thrid\n";
my @aa=('a','b','b','c','b','d','e','f','b','g','e','g','a');
print "primer \@aa is @aa\n";
for (@aa) {$aa{$_}=0;}
my @aa=sort {$a<=>$b} keys %aa;
@bb=sort(@aa);
print @bb,"\n";
 楼主| 发表于 2003-12-15 14:06:34 | 显示全部楼层

谢啦,兄弟们

我要好好看看这些Perl源码才行。呵呵。
您需要登录后才可以回帖 登录 | 注册

本版积分规则

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