数组中有一个数字出现的次数超过了数组长度的一半，找出这个数

这道题实际上不难，用很笨的方法也是能解答出来的，但是浪费了程序的时间和空间，从网上查到一种思路，觉得不错。
        有个数字出现的次数超过了数组长度的一半，也就是，有个数字出现的次数比其他所有数字出现次数的和还要多。遍历数组时保存连个值，一个是数组中的数字，一个是出现的次数，遍历到一个数字时，如果该数字和之前保存的数字相同，则次数加一，如果该数字和之前保存的数字不同，则次数减一，如果次数为零，遍历下一个数组元素，并把次数设为一。要找的数字肯定是最后一次把次数设为1时对应的数字。
 
#include   <iostream> 
using   namespace   std; 
bool g_bInputInvalid = false; 
int MoreThanHalfNum(int* numbers, unsigned int length) 
{ 
    if(numbers == NULL && length == 0) 
    { 
        g_bInputInvalid = true; 
        return 0; 
    } 
    g_bInputInvalid = false; 
    int result = numbers[0]; 
    int times = 1; 
    for(int i = 1; i < length; ++i) 
    { 
        if(times == 0) 
        {   result = numbers[i]; 
            times = 1; 
        } 
        else if(numbers[i] == result) 
            times++; 
        else
            times--; 
    } 
    // verify whether the input is valid 
    times = 0; 
    for( int i = 0; i < length; ++i) 
    { 
        if(numbers[i] == result) 
            times++; 
    } 
    if(times * 2 <= length) 
    { 
        g_bInputInvalid = true; 
        result = 0; 
    } 
    return result; 
} 
void main() 
{ 
    int a[]={1,2,2,3,4,5,2,2,2}; 
    int re=MoreThanHalfNum(a,9); 
    cout<<re; 
} 

作者“菜鸟变身记”

补充：软件开发 , C语言 ,

上一个：C语言头文件组织
下一个：贪食蛇游戏