数组中出现次数超过一半的数字

数组数字超过了一半，意味着这个数字出现的次数比其它数字的总和还要多。假设所有数字中不相等的可以两两抵消，那最后剩下来的肯定是那个超过一半的数字。利用这个思路，先记录第一个数组元素为a，并记录出现次数为1，如何接下来的数组元素和a相同，则num++，如果不相同，则num--，如果num ==0 时，则重新记录新的数组元素，并初始化num为1. 如果存在超过一半的数字，那么这个数字必定是a，但是有一种情况，如数组为{1,2,3},那么1,2相互抵消，剩下a=3,num=1,但是3并不是那个超过一半的数字，所以还必须重新循环判断a存在的个数是否超过了数组的一半长度。如果是，则记录输出。
这里的isvalid是用来标记是否是有超过一半的数字存在，在入参错误或者没有的情况下，这个字为false。

#include <stdio.h>
#include <stdlib.h>
#define bool int
#define false 0
#define true 1

bool isvalid = false;
int MoreThanHalfNum(int* numbers, int length)
{
    int i;
    int a,num;
    if(numbers == NULL || length <= 0) {
        return 0;
    }
    a = numbers[0];
    num = 1;
    for (i = 1; i < length; i++) {
        if(num == 0) {
            a = numbers[i];
            num=1;
        }
        else if(a == numbers[i]) {
            num++;
        }else {
            num--;
        }
    }
    num = 0;
    for(i = 0; i < length; i++) {
        if(numbers[i] == a)
            num++;
    }
    if(num > length/2) {
        isvalid = true;
        return a;
    }
    return 0;
    /*this judge is false when a[] = {1,3,2}
     * if(num >= 1) {
        isvalid = true;
        return a;
    }else
        return 0;
    */
}
int main(int argc, char*argv[])
{
    int a1[] = {2,2,1,1,2};
    int a2[] = {1,2,2,1,1};
    int a3[] = {1,1,2,2};
    int a4[] = {1,3,2};
    int result;
    result = MoreThanHalfNum(a1,sizeof(a1)/sizeof(int));
    if(isvalid)
        printf("more than half num of a1 is %d\n",result);
    else
        printf("no more than half num in the array a1\n");

    isvalid = false;
    result = MoreThanHalfNum(a2,sizeof(a2)/sizeof(int));
    if(isvalid)
        printf("more than half num of a2 is %d\n",result);
    else
        printf("no more than half num in the array a2\n");

    isvalid = false;
    result = MoreThanHalfNum(a3,sizeof(a3)/sizeof(int));
    if(isvalid)
        printf("more than half num of a3 is %d\n",result);
    else
        printf("no more than half num in the array a3\n");

    isvalid = false;
    result = MoreThanHalfNum(a4,sizeof(a4)/sizeof(int));
    if(isvalid)
        printf("more than half num of a4 is %d\n",result);
    else
        printf("no more than half num in the array a4\n");

    return 0;
}

运行结果

more than half num of a1 is 2
more than half num of a2 is 1
no more than half num in the array a3
no more than half num in the array a4