// 面试题39：数组中出现次数超过一半的数字// 题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例// 如输入一个长度为9的数组{1, 2, 3, 2, 2, 2, 5, 4, 2}。由于数字2在数组中// 出现了5次，超过数组长度的一半，因此输出2。#include 
     
      using namespace std;/*Random Partition*/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 == nullptr || length <= 0 || start < 0 || end >= length)        throw new exception("Invalid Parameters");    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 == nullptr && length <= 0)        g_bInputInvalid = true;    return g_bInputInvalid;}bool CheckMoreThanHalf(int* numbers, int length, int number)//检查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;}// ====================方法1====================//受快排启发，进行一轮快排，看本轮的中点是在数组的哪部分，具体分三种情况int MoreThanHalfNum_Solution1(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)//如果index == middle，那么说明numbers[middle]超过一半，注意这个判断条件中，index和middle不随迭代而改变    {        if (index > middle)//如果index != middle，且index > middle，则在index左边        {            end = index - 1;            index = Partition(numbers, length, start, end);        }        else//如果index != middle，且index < middle，则在index右边        {            start = index + 1;            index = Partition(numbers, length, start, end);        }    }    int result = numbers[middle];    if (!CheckMoreThanHalf(numbers, length, result))//必须检查，有可能不是        result = 0;    return result;}// ====================方法2====================//这个比较复杂，就是下一值如果和当前值一致，count就+1,否则-1，如果为0，则舍弃记录当前值，改下一值，最后+1的值可能会超过一半int MoreThanHalfNum_Solution2(int* numbers, int length){    if (CheckInvalidArray(numbers, length))        return 0;    int result = numbers[0];//初试为第一个值    int times = 1;//初试为1    for (int i = 1; i < length; ++i)    {        if (times == 0)//改记录下一值        {            result = numbers[i];            times = 1;        }        else if (numbers[i] == result)            times++;        else            times--;    }    if (!CheckMoreThanHalf(numbers, length, result))        result = 0;    return result;}// ====================测试代码====================void Test(const char* testName, int* numbers, int length, int expectedValue, bool expectedFlag){    if (testName != nullptr)        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_Solution1(numbers, length);    if (result == expectedValue && g_bInputInvalid == expectedFlag)        printf("Passed.\n");    else        printf("Failed.\n");    printf("Test for solution2: ");    result = MoreThanHalfNum_Solution2(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 };    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", nullptr, 0, 0, true);}int main(int argc, char* argv[]){    Test1();    Test2();    Test3();    Test4();    Test5();    Test6();    system("pause");    return 0;}