카테고리 없음

sort with same string together

fw93 2018. 3. 26. 12:55

근데 같은 것끼리 짝지으라고 했지 굳이 string array를 sort 하라고 안 했으니까, buffer을 multi key hash table로 짜면 성능상 훨신 이득이 있다

klogk * N + N (끝)


1
2
3
4
5
6
7
8
9
10
11
12
void sortstrings(vector<string> & data) {
    unordered_multimap<string, string> tmp;
    for (int i = 0; i < data.size(); i++) {
        string s = data.at(i);
        sort(begin(s), end(s));
        tmp.insert(pair<string, string>(s, data.at(i)));
    }
    int i = 0;
    for (unordered_multimap<string, string>::iterator it = tmp.begin(); it != tmp.end(); it++, i++) {
        data[i] = (*it).second;
    }
}
cs


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
void sortstrings3(vector<string> & data) {
    multimap<string, string> tmp;
    for (int i = 0; i < data.size(); i++) {
        string s = data.at(i);
        sort(begin(s), end(s));
        tmp.insert(pair<string, string>(s, data.at(i)));
    }
    int i=0;
    for (multimap<string, string>::iterator it = tmp.begin(); it != tmp.end(); i++, it++) {
        data[i] = (*it).second;
    }
}
 
 
bool comparitor(string s1, string s2) {
    sort(begin(s1), end(s1));
    sort(begin(s2), end(s2));
    return s1 > s2;
}
 
void sortstrings(vector<string> & data) {
    sort(data.begin(),data.end(), comparitor);
}
 
 
 
void sortstrings2(vector<string> &data) {
    vector<pair<string,string>> *tmp = new vector<pair<string,string>>();
    for (int i = 0; i < data.size(); i++) {
        string s = data.at(i);
        sort(begin(s), end(s));
        tmp->push_back(pair<string, string>(s, data.at(i)));
    }
    sort(tmp->begin(), tmp->end());
    for (int i = 0; i < tmp->size(); i++) {
        data[i] = tmp->at(i).second;
    }
}
 
 
int main9() {
    vector<string> v1 = { "asdasd","ddwdwd","gwegweg","aabbc","cbbaa","gwerewgew","bbcaa","ewqeqweqwe" };
    sortstrings3(v1);
    for (string s : v1) {
        cout << s << endl;
    }
    while (1) {};
    return 0;
}
cs


저작자표시 (새창열림)