數組中出現次數超過一半的數字

題目：數組中有一個數字出現的次數超過了數組長度的一半，找出這個數字。

思路：一個數字在數組中出現次數超過了一半，則排序後，位於數組中間的數字一定就是該出現次數超過了長度一半的數字（，也即是說，這個數字就是統計學上的中位數。事實上可以不用對數組進行排序，或者說僅部分排序，受快速排序的partition函數的啟發，我們可以利用反復調用partition函數來求的該數字。我們現在數組中隨機選取一個數字，而後通過Partition函數返回該數字在數組中的索引index，如果index剛好等於n/2，則這個數字便是數組的中位數，也即是要求的數，如果index大於n/2，則中位數肯定在index的左邊，在左邊繼續尋找即可，反之在右邊尋找。這樣可以只在index的一邊尋找，而不用兩邊都排序，減少了一半排序時間。

#include<stdio.h>
#include<iostream>
#include<stdlib.h>

//生成一個在start和end之間的隨機數
int RandomInRange(int min, int max)
{
int random = rand() % (max - min + 1) + min;
return random;
}

//交換兩個數
void Swap(int* num1, int* num2)
{
int temp = *num1;
*num1 = *num2;
*num2 = temp;
}

//選擇一個數字，把數組分成兩部分
int Partition(int data[], int length, int start, int end)
{
if(data == NULL || length <= 0 || start < 0 || end >= length)
// throw new std::exception("Invalid Parameters");
exit(1);

int index = RandomInRange(start, end);
Swap(&data[index], &data[end]);

int small = start - 1;
for(index = start; index < end; ++ index)
{
if(data[index] < data[end])
{
++ small;
if(small != index)
Swap(&data[index], &data[small]);
}
}

++ small;
Swap(&data[small], &data[end]);

return small;
}

bool g_bInputInvalid = false;

//檢查輸入數組的有效性
bool CheckInvalidArray(int* numbers, int length)
{
g_bInputInvalid = false;
if(numbers == NULL && length <= 0)
g_bInputInvalid = true;

return g_bInputInvalid;
}

//檢查輸入數組中出現最高的數字次數是否超過數組長度的一半
bool CheckMoreThanHalf(int* numbers, int length, int number)
{
int times = 0;
for(int i = 0; i < length; ++i)
{
if(numbers[i] == number)
times++;
}

bool isMoreThanHalf = true;
if(times * 2 <= length)
{
g_bInputInvalid = true;
isMoreThanHalf = false;
}

return isMoreThanHalf;
}

int MoreThanHalfNum(int* numbers, int length)
{
if(CheckInvalidArray(numbers, length))
return 0;

int middle = length >> 1;
int start = 0;
int end = length - 1;
int index = Partition(numbers, length, start, end);
while(index != middle)
{
if(index > middle)
{
end = index - 1;
index = Partition(numbers, length, start, end);
}
else
{
start = index + 1;
index = Partition(numbers, length, start, end);
}
}

int result = numbers[middle];
if(!CheckMoreThanHalf(numbers, length, result))
result = 0;

return result;
}

int main()
{
int numbers[] = {1,2,3,2,2,2,5,4,2};
int length = sizeof(numbers) / sizeof(int);
printf("Test for solution: ");
int result = MoreThanHalfNum(numbers, length);
if(g_bInputInvalid == false)
printf("%d \n", result);
else
printf("Failed.\n");
}