算法题目---数组中出现次数超过一半的数字

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

#include<iostream>

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

using namespace std;


bool g_bInputInvalid = false;

bool CheckInvalidArray(int *num,int len)
{
     g_bInputInvalid = false;
    if(num == NULL && len <= 0)
        g_bInputInvalid = true;
    return g_bInputInvalid;
}

bool CheckMoreThanHalf(int *nums,int len,int num)
{
    int times = 0;
    for(int i = 0;i<len;++i)
    {
        if(nums[i] == num)
            times++;
    }
    bool isMoreThanHalf = true;
    
    if(times * 2 <= len)
    {
        isMoreThanHalf =false;
        g_bInputInvalid = true;
    }
    return isMoreThanHalf;
}

int RandomInRange(int min,int max)
{
    int random = rand() % (max - min + 1) + min;
    return random;
}

void Swap(int *num1,int *num2)
{
    int tmp = *num1;
    *num1 = *num2;
    *num2 = tmp;
}

int Partition(int data[],int len,int start,int end)
{
    if(data == NULL || len <= 0 || start < 0 || end >= len)
        printf("error\n");
    
    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;
}

int MoreThanHalfNum_1(int *nums,int len)
{
    if(CheckInvalidArray(nums,len))
        return 0;
    
    int mid = len >> 1;
    int start = 0;
    int end = len -1;
    
    int index = Partition(nums,len,start,end);
    while(index != mid)
    {
        if(index > mid)
        {
            end = index -1 ;
            index = Partition(nums,len,start,end);
        }
        else
        {
            start = index +1;
            index = Partition(nums,len,start,end);
        }
    }    
    int ret = nums[mid];
     if(!CheckMoreThanHalf(nums, len, ret))
        ret = 0;

    return ret;

    
}

int MoreThanHalfNum_2(int *nums,int len)
{
     if(CheckInvalidArray(nums, len))
        return 0;
     int ret = nums[0];
     int times = 1;
     for(int i=1;i<len;++i)
    {
        if(times == 0)
        {
            ret = nums[i];
            times = 1;
        }
        else if(nums[i] == ret)
            times++;
        else
            times--;
    }

    if(!CheckMoreThanHalf(nums, len, ret))
        ret = 0;
 
    return ret;
}

void Test(char* testName, int* numbers, int length, int expectedValue, bool expectedFlag)
{
    if(testName != NULL)
        printf("%s begins: \n", testName);

    int* copy = new int[length];
    for(int i = 0; i < length; ++i)
        copy[i] = numbers[i];

    printf("Test for solution1: ");
   int  result = MoreThanHalfNum_1(numbers, length);
    if(result == expectedValue && g_bInputInvalid == expectedFlag)
        printf("Passed.\n");
    else
        printf("Failed.\n");

    printf("Test for solution2: ");
     result = MoreThanHalfNum_2(copy, length);
    if(result == expectedValue && g_bInputInvalid == expectedFlag)
        printf("Passed.\n");
    else
        printf("Failed.\n");

    delete[] copy;
}

void Test1()
{
    int numbers[] = {1, 2, 3, 2, 2, 2, 5, 4, 2};
    Test("Test1", numbers, sizeof(numbers) / sizeof(int), 2, false);
}

void Test2()
{
    //int numbers[] = {1, 2, 3, 2, 4, 2, 5, 2, 3};
    int numbers[] = {1, 2, 3, 4, 8, 2, 5, 2, 3};
    Test("Test2", numbers, sizeof(numbers) / sizeof(int), 0, true);
}

void Test3()
{
    int numbers[] = {2, 2, 2, 2, 2, 1, 3, 4, 5};
    Test("Test3", numbers, sizeof(numbers) / sizeof(int), 2, false);
}

void Test4()
{
    int numbers[] = {1, 3, 4, 5, 2, 2, 2, 2, 2};
    Test("Test4", numbers, sizeof(numbers) / sizeof(int), 2, false);
}

void Test5()
{
   int numbers[] = {1};
   Test("Test5", numbers, 1, 1, false);
}

void Test6()
{
    Test("Test6", NULL, 0, 0, true);
}

int main()
{
   // Test1();
    Test2();
   /* Test3();
    Test4();
    Test5();
    Test6();
*/
    return 0;
}