《Cracking the Coding Interview》——第11章：排序和搜索—

《Cracking the Coding Interview》——第11章：排序和搜索——题目2

2014-03-21 20:49

题目：设计一种排序算法，使得anagram排在一起。

解法：自定义一个comparator，使用额外的空间来统计字母个数，然后比较字母个数。

代码：

 1 // 11.2 Sort an array of strings such that anagrams stay next to each other.
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <string>
 5 #include <vector>
 6 using namespace std;
 7 
 8 string ta, tb;
 9 int counting[256];
10 
11 void countingSort(string &s)
12 {
13     int i, j;
14 
15     for (i = 0; i < 256; ++i) {
16         counting[i] = 0;
17     }
18     for (i = 0; i < (int)s.length(); ++i) {
19         ++counting[s[i]];
20     }
21     s.clear();
22 
23     for (i = 0; i < 256; ++i) {
24         for (j = 0; j < counting[i]; ++j) {
25             s.push_back(i);
26         }
27     }
28 }
29 
30 bool anagramComparator(const string &a, const string &b)
31 {
32     ta = a;
33     tb = b;
34     sort(ta.begin(), ta.end());
35     sort(tb.begin(), tb.end());
36 
37     return ta < tb;
38 }
39 
40 int main()
41 {
42     vector<string> v;
43     int i;
44     int n;
45 
46     while (cin >> n && n > 0) {
47         v.resize(n);
48         for (i = 0; i < n; ++i) {
49             cin >> v[i];
50         }
51         sort(v.begin(), v.end(), anagramComparator);
52         for (i = 0; i < n; ++i) {
53             if (i > 0) {
54                 cout << ' ';
55             }
56             cout << v[i];
57         }
58         cout << endl;
59     }
60     
61     return 0;
62 }