面试题29：数组中出现次数超过一半的数字

 1 bool g_bInputInvalid = false;
 2 
 3 bool CheckInvalidArray(int* numbers, int length)
 4 {
 5     g_bInputInvalid = false;
 6     if(numbers == NULL && length <= 0)
 7         g_bInputInvalid = true;
 8 
 9     return g_bInputInvalid;
10 }
11 
12 bool CheckMoreThanHalf(int* numbers, int length, int number)
13 {
14     int times = 0;
15     for(int i = 0; i < length; ++i)
16     {
17         if(numbers[i] == number)
18             times++;
19     }
20 
21     bool isMoreThanHalf = true;
22     if(times * 2 <= length)
23     {
24         g_bInputInvalid = true;
25         isMoreThanHalf = false;
26     }
27 
28     return isMoreThanHalf;
29 }
30 
31 int MoreThanHalfNum_Solution2(int* numbers, int length)
32 {
33     if(CheckInvalidArray(numbers, length))
34         return 0;
35  
36     int result = numbers[0];
37     int times = 1;
38     for(int i = 1; i < length; ++i)
39     {
40         if(times == 0)
41         {
42             result = numbers[i];
43             times = 1;
44         }
45         else if(numbers[i] == result)
46             times++;
47         else
48             times--;
49     }
50  
51     if(!CheckMoreThanHalf(numbers, length, result))
52         result = 0;
53  
54     return result;
55 }