思路：一個數字在數組中出現次數超過了一半，則排序後，位於數組中間的數字一定就是該出現次數超過了長度一半的數字（，也即是說，這個數字就是統計學上的中位數。事實上可以不用對數組進行排序，或者說僅部分排序，受快速排序的partition函數的啟發，我們可以利用反復調用partition函數來求的該數字。我們現在數組中隨機選取一個數字，而後通過Partition函數返回該數字在數組中的索引index，如果index剛好等於n/2，則這個數字便是數組的中位數，也即是要求的數，如果index大於n/2，則中位數肯定在index的左邊，在左邊繼續尋找即可，反之在右邊尋找。這樣可以只在index的一邊尋找，而不用兩邊都排序，減少了一半排序時間。
1 #include<stdio.h>
2 #include<iostream>
3 #include<stdlib.h>
4
5 //生成一個在start和end之間的隨機數
6 int RandomInRange(int min, int max)
7 {
8 int random = rand() % (max - min + 1) + min;
9 return random;
10 }
11
12 //交換兩個數
13 void Swap(int* num1, int* num2)
14 {
15 int temp = *num1;
16 *num1 = *num2;
17 *num2 = temp;
18 }
19
20 //選擇一個數字，把數組分成兩部分
21 int Partition(int data[], int length, int start, int end)
22 {
23 if(data == NULL || length <= 0 || start < 0 || end >= length)
24 // throw new std::exception("Invalid Parameters");
25 exit(1);
26
27 int index = RandomInRange(start, end);
28 Swap(&data[index], &data[end]);
29
30 int small = start - 1;
31 for(index = start; index < end; ++ index)
32 {
33 if(data[index] < data[end])
34 {
35 ++ small;
36 if(small != index)
37 Swap(&data[index], &data[small]);
38 }
39 }
40
41 ++ small;
42 Swap(&data[small], &data[end]);
43
44 return small;
45 }
46
47 bool g_bInputInvalid = false;
48
49 //檢查輸入數組的有效性
50 bool CheckInvalidArray(int* numbers, int length)
51 {
52 g_bInputInvalid = false;
53 if(numbers == NULL && length <= 0)
54 g_bInputInvalid = true;
55
56 return g_bInputInvalid;
57 }
58
59 //檢查輸入數組中出現最高的數字次數是否超過數組長度的一半
60 bool CheckMoreThanHalf(int* numbers, int length, int number)
61 {
62 int times = 0;
63 for(int i = 0; i < length; ++i)
64 {
65 if(numbers[i] == number)
66 times++;
67 }
68
69 bool isMoreThanHalf = true;
70 if(times * 2 <= length)
71 {
72 g_bInputInvalid = true;
73 isMoreThanHalf = false;
74 }
75
76 return isMoreThanHalf;
77 }
78
79
80 int MoreThanHalfNum(int* numbers, int length)
81 {
82 if(CheckInvalidArray(numbers, length))
83 return 0;
84
85 int middle = length >> 1;
86 int start = 0;
87 int end = length - 1;
88 int index = Partition(numbers, length, start, end);
89 while(index != middle)
90 {
91 if(index > middle)
92 {
93 end = index - 1;
94 index = Partition(numbers, length, start, end);
95 }
96 else
97 {
98 start = index + 1;
99 index = Partition(numbers, length, start, end);
100 }
101 }
102
103 int result = numbers[middle];
104 if(!CheckMoreThanHalf(numbers, length, result))
105 result = 0;
106
107 return result;
108 }
109
110 int main()
111 {
112 int numbers[] = {1,2,3,2,2,2,5,4,2};
113 int length = sizeof(numbers) / sizeof(int);
114 printf("Test for solution: ");
115 int result = MoreThanHalfNum(numbers, length);
116 if(g_bInputInvalid == false)
117 printf("%d \n", result);
118 else
119 printf("Failed.\n");
120 }
