問題：一個大小為n的數組，里面的數有重復，要求找出數量超過一半的那個數。
傳統方法就不說了，排序然后順序掃描查找，復雜度為O(nlogn + n) = O(nlogn)，有些慢。
《編程之美》上提供的方法是掃描數組，每次消去兩個不相同的數，這樣，到最后剩下的數必定是所求的數，證明非常簡單，略了。
關鍵問題是編碼，如果寫不好容易些成O(n
2)復雜度的，書上的寫法不錯：
1 int find_messager(int *id, int n) {
2 assert(id != NULL);
3 int i;
4 int times = 1;
5 int messager = id[0];
6 for (i = 1; i < n; ++i) {
7 if (times == 0) {
8 messager = id[i];
9 times = 1;
10 } else {
11 if (messager == id[i]) {
12 times++;
13 } else {
14 times--;
15 }
16 }
17 }
18 return messager;
19 }
擴展問題來了，如果有三個數，他們各自的總數都查過了n/4，那么怎么找出這三個數呢？
其實和上面解法類似，只不過是用三個標記就可以了，代碼如下：
1 struct Messager {
2 int id[4];
3 };
4
5 Messager *find_messagers(int *id, int n) {
6 assert(id != NULL);
7 Messager *msgr = new Messager;
8 memset(msgr, 0, sizeof(Messager));
9 int times[4] = {0, 0, 0, 0};
10 int i, j;
11 for (i = 0; i < n; ++i) {
12 for (j = 1; j < 4; ++j) {
13 if (times[j] > 0 && msgr->id[j] == id[i]) {
14 times[j]++;
15 break;
16 }
17 }
18
19 if (j == 4) {
20 for (j = 1; j < 4; ++j) {
21 if (times[j] == 0) {
22 times[j]++;
23 msgr->id[j] = id[i];
24 break;
25 }
26 }
27 if (j == 4) {
28 times[1]--;
29 times[2]--;
30 times[3]--;
31 }
32 }
33 }
34 return msgr;
35 }
這種思想非常清晰，并且實現非常巧妙！
posted on 2012-09-04 15:06
myjfm 閱讀(642)
評論(0) 編輯 收藏 引用 所屬分類:
算法基礎