問題：一個(gè)大小為n的數(shù)組，里面的數(shù)有重復(fù)，要求找出數(shù)量超過一半的那個(gè)數(shù)。
傳統(tǒng)方法就不說了，排序然后順序掃描查找，復(fù)雜度為O(nlogn + n) = O(nlogn)，有些慢。
《編程之美》上提供的方法是掃描數(shù)組，每次消去兩個(gè)不相同的數(shù)，這樣，到最后剩下的數(shù)必定是所求的數(shù)，證明非常簡(jiǎn)單，略了。
關(guān)鍵問題是編碼，如果寫不好容易些成O(n
2)復(fù)雜度的，書上的寫法不錯(cuò)：
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 }
擴(kuò)展問題來了，如果有三個(gè)數(shù)，他們各自的總數(shù)都查過了n/4，那么怎么找出這三個(gè)數(shù)呢？
其實(shí)和上面解法類似，只不過是用三個(gè)標(biāo)記就可以了，代碼如下：
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 }
這種思想非常清晰，并且實(shí)現(xiàn)非常巧妙！
posted on 2012-09-04 15:06
myjfm 閱讀(637)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
算法基礎(chǔ)