[程序设计]比较数组(一)

cnangel

响应一些人的建议，提高一些人的编程兴趣。
题目:
数组下标最大为n;可能数组中有未知相同的元素
要求:
        1 分别用C、Perl、PHP语言；
        2 对相同元素只保留其中的一个，即无重复元素；
        3 效率最高，比如n为100万左右时，采用的方法最简洁且高效。

注意:
        1 不考虑数组的复杂的数据结构,只考虑字符串类型和整形(16/10/8/2进制)
        2 编程思路好的或者效率高的同学将获得免费大餐一顿赞助商:陈绪(linuxmine)
        3 为了规范市场,一律无代码的回复全部删除.
        4 对代码使用［code］［/code］标签为最棒的

[ 本帖最后由 cnangel 于 2007-4-6 12:58 编辑 ]

800

对原有数组a[n]进行排序
新建数组b[n]
b[0] = a[0]；
int j = 0；
for(int k = 1; k < n; k++)
{
    if (a[k] > b[j])
    {
        j++；
        b[j] = a[k];
    }
    else
    {
         continue;
    }
}

这个思路如何？？？？

[ 本帖最后由 800 于 2007-4-5 11:18 编辑 ]

cnangel

1. #!/usr/bin/perl
   
2. 
   
3. use strict;
   
4. my $hash = {};
   
5. #假设@array是有下标为n的数组
   
6. my @array = (a1, a2 ... an);
   
7. 
   
8. for (my $i = 0; $i < $#array; $i ++)
   
9. {
   
10.     # defined @array value and hash key(value is not important)
    
11.     $hash{$array[$i]} = 0;
    
12. }
    
13. print keys(%$hash);#即为要得到的数组.

复制代码

cnangel

看看cuci的办法:代他发贴

1. my @array = qw(a1...an);
   
2. my %hash;
   
3. my @newarray = grep { ++$hash{$_} < 2 } @array;

复制代码

root1982

大概的说，我觉得hash是最好的选择，但是c就麻烦了，没有现成的hash。如果先排序，复杂性就是n*log(n)。像"800"的思路。

假设是整数，最大值不会远大于n。先找出最大值

1. void remove_dup(int a[], int n){
   
2.     int i;
   
3.     int max=a[0];
   
4.     for(i=1; i<n; i++) //找到最大值
   
5.         if(a[i]>max)
   
6.             max=a[i];
   
7.     int b[max];
   
8.     for(i=0; i<max; i++)
   
9.          b[i]=0;
   
10.     //hash
    
11.     for(i=0; i<n; i++){
    
12.         b[a[i]]=1;
    
13.     }
    
14.         
    
15.     for(i=0; i<max; i++){
    
16.        if(b[i]!=0)
    
17.             printf("%d ", b[i]); //输出结果
    
18.    }
    
19. }

复制代码

复杂性控制在：常数*n

[ 本帖最后由 root1982 于 2007-4-10 02:39 编辑 ]

cnangel

同志们啊,还凑不上一桌啊  

root1982

原帖由 cnangel 于 2007-4-7 08:48 发表
看看cuci的办法:代他发贴

my @array = qw(a1...an);
my %hash;
my @newarray = grep { ++$hash{$_} < 2 } @array;

看完这个我更加坚信perl是一个牛的东西。 能解释一下吗。每个字单着看都明白，放一块就不懂了

cnangel

这个就是比我多用了一个数组@newarray，看我的方法，如果处理大文件，当然还是我的方法好，因为少复制一次内存

$hash{$_}是一个统计相同个数的散列变量，如果大于等于2就说明以前有这个$_了

一般变量未指定值时候，缺省值为空，做加减运算时空代表了0，有点eval的味道

root1982

我看我还是别在简历上说自己会perl了

cnangel

  太极端