这道题最简单实用的算法就是顺序统计，注意题目中空间限制的“Memory Limit: 65536K”，摆明了就是用空间换时间。设一个大小为10000000的int型数组（注意：千万要用int型，我一开始小家子气，用了char型想省点空间，后来发现有重复次数超过128的，查了好久才发现...sigh...）
算法复杂度是线性的，肯定不会慢。

常见错误分析：
1.无重复时的“No duplicates.”（碰到字符串输出，不要自己打，ctrl+C,ctrl+V）
2.记录输入号码的字符串大小要设大一点，char str[100]肯定够了
3.注意号码中数字“0”出现在头部时要注意补齐
4.GCC和G++还是有差距的，不要用cin,cout,尽量用scanf,printf

附上顺序统计方法的C语言实现：
（其实非常简单，根本用不着排序，也用不到任何复杂的数据结构，一个大数组全部搞定了，时间也还算勉强能够接受）

#include <stdio.h>
#include <string.h>

int record_times[10000000];

void convert(char* tel, char *result )
{
    int i;
    int index;
    result[3] = '-';
    index = 0;
    for ( i=0; i<strlen(tel); i++ ){
        if (index==3) index++;
        switch ( tel[i] ){
            case 'A':case 'B':case 'C':result[index++] = '2'; break;
            case 'D':case 'E':case 'F':result[index++] = '3'; break;
            case 'G':case 'H':case 'I':result[index++] = '4'; break;
            case 'J':case 'K':case 'L':result[index++] = '5'; break;
            case 'M':case 'N':case 'O':result[index++] = '6'; break;
            case 'P':case 'R':case 'S':result[index++] = '7'; break;
            case 'T':case 'U':case 'V':result[index++] = '8'; break;
            case 'W':case 'X':case 'Y':result[index++] = '9'; break;
            case '-': break;
            case '1':case '2':case '3':case '4':case '5':
            case '6':case '7':case '8':case '9':case '0': result[index++] = tel[i]; break;
            default: break;
        }
    }
    result[8] = '\0';
}

int num(char *tel)
{
    int i;
    int n=0;

    for ( i=0; i<strlen(tel); i++ )
        if ( tel[i]>='0' && tel[i]<='9' )
            n = n * 10 + ( tel[i] - 48 );
    return n;
}

void toTel( int num, char *tel )
{
    int index;

    memset( tel, '0', 8 );
    tel[8] = '\0';
    tel[3] = '-';
    index = 7;
    while ( num ) {
        if ( index == 3 ) index--;
        tel[index--] = num % 10 + 48;
        num /= 10;
    }
}

int main()
{
    int i;
    int n;
    char tel[500];
    char real_tel[9];
    int index;
    int flag;

    scanf("%d",&n);
    for ( i=0; i<n; i++ ){
        scanf("%s",tel);
        convert(tel,real_tel);
        index = num(real_tel);
        record_times[index] ++;
    }
    flag = 0;
    for ( i=0; i<10000000; i++ )
        if ( record_times[i] > 1 ){
            toTel(i,tel);
            printf("%s %d\n",tel,record_times[i]-0);
            flag = 1;
        }
    if ( flag == 0 )
        printf("No duplicates.\n");

    return 0;
}

• Re:1002总结 (1262) lhdtigerblue 2010-08-01 14:15:28
• Re:1002总结 (324) lhdtigerblue 2010-08-01 14:37:53
• Re:1002总结 (433) lhdtigerblue 2010-08-01 14:39:24