一堆数字里有一个数字占了全部数字的一半以上，另外的数字都是随机的，快速找到这个数字

caniadate.c

/*
 * 一堆数字里有一个数字占了全部数字的一半以上，另外的数字都是随机的，
 * 快速找到这个数字
 *
 * 算法来自 http://segmentfault.com/q/1010000000187028
 * 由递归改为循环
 * 时间复杂度 O(n - m)
 */

#include <stdio.h>

#define SIZE(arr) sizeof(arr) / sizeof(*arr)

#define TYPE int

TYPE candiadate(TYPE a[], int m, int n, TYPE cand)
{
    TYPE c = a[m];
    int count = 1;
    int j = m;
    for (;;) {
        c = a[j];
        count = 1;
        for (++j; j < n && count > 0; ++j) {
            if (a[j] == c) {
                ++count;
            }
            else {
                --count;
            }
        }
        if (j == n) {
            return (count == 0) ? cand : c;
        }
    }
    return -1;
}

int main()
{
    int is[] = {1, 2, 3, 0, 9, 0, 3, 0, 0, 0, 0, 1, 0, 0, 2, 0, 0, 0, 0, 2, 0};
    int h[] = {1,2,1,1,2,1, 2};
    
    printf("%d\n", candiadate(is, 0, SIZE(is), 1023));
    printf("%d\n", candiadate(h, 0, SIZE(h), 1023));

    return 0;
}