问题：一个大小为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 阅读(621)
评论(0) 编辑 收藏 引用 所属分类:
算法基础