无耻了下，用了下map，嘿嘿～

可是总是超时，不明白，不考虑map内部算法的话，复杂度是O(N)没错啊。

我自己写了个输入文件生成器，生成了个100000条记录的文件，当条目形如：
--W-A--A--C-T-0-5--
这样的时候，运行时间粗略估计1s左右，

只有当条目形如：
--------------------O-----------------------------------------------H--P---------------------------------------------------------------------V-----------------------------------------------------------------N-------------------------M----------------T-
这样的时候，运行时间大概7s左右。

可是提交上去，总是TLE，悲剧。。。。难道OJ上的测试数据真的这么变态？

下面是我的代码：
=========================================
#include <iostream>
#include <string>
#include <map>
using namespace std;

typedef map<string, int> Dictionary;

void formatString (string& str) {
    for (string::iterator iter = str.begin (); iter < str.end ();) {
        switch (*iter) {
            case '-':
                str.erase (iter);
                continue;
            case 'A':
            case 'B':
            case 'C':
                str.replace (iter, iter + 1, "2");
                break;
            case 'D':
            case 'E':
            case 'F':
                str.replace (iter, iter + 1, "3");
                break;
            case 'G':
            case 'H':
            case 'I':
                str.replace (iter, iter + 1, "4");            
                break;
            case 'J':
            case 'K':
            case 'L':
                str.replace (iter, iter + 1, "5");
                break;
            case 'M':
            case 'N':
            case 'O':
                str.replace (iter, iter + 1, "6");
                break;
            case 'P':
            case 'R':
            case 'S':
                str.replace (iter, iter + 1, "7");
                break;
            case 'T':
            case 'U':
            case 'V':
                str.replace (iter, iter + 1, "8");
                break;
            case 'W':
            case 'X':
            case 'Y':
                str.replace (iter, iter + 1, "9");
                break;
            default:
                break;
        }
        iter++;
    }
}

int main (int argc, char** argv) {
    Dictionary telephones;

    int repeat;
    string telephone;

    cin >> repeat;
    while (repeat-- > 0) {
        cin >> telephone;
        formatString (telephone);
        telephones[telephone]++;
#ifdef _DEBUG_
        cout << "_DEBUG_:" << telephone << " " << endl;
#endif        
    }

    bool noDup = true;
    
    for (Dictionary::iterator iter = telephones.begin ();
         iter != telephones.end ();
         iter++) {

        
        if ((*iter).second > 1) {
            string temp = (*iter).first;
            cout << temp.insert (3, "-") << " " << (*iter).second << endl;
            noDup = false;
        }
    }

    if (noDup) {
        cout << "No duplicates." << endl;
    }
    return 0;
}

• Re:TLE了，大牛帮忙解释一下吧 ~_~ (17) sweetdum 2011-06-17 11:25:22