《剑指offer》第三十九题（数组中出现次数超过一半的数字）

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

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

// 如输入一个长度为9的数组{1, 2, 3, 2, 2, 2, 5, 4, 2}。由于数字2在数组中

// 出现了5次，超过数组长度的一半，因此输出2。

#include <iostream>

using namespace std;

/*Random Partition*/

int RandomInRange(int min, int max)

{

    int random = rand() % (max - min + ) + 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 <=  || start <  || end >= length)

        throw new exception("Invalid Parameters");

    int index = RandomInRange(start, end);//生成随机点

    Swap(&data[index], &data[end]);//放到最后

    int small = start - ;

    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 <= )

        g_bInputInvalid = true;

    return g_bInputInvalid;

}

bool CheckMoreThanHalf(int* numbers, int length, int number)//检查number在数列中是否超过一半

{

    int times = ;

    for (int i = ; i < length; ++i)

    {

        if (numbers[i] == number)

            times++;

    }

    bool isMoreThanHalf = true;

    if (times *  <= length)

    {

        g_bInputInvalid = true;

        isMoreThanHalf = false;

    }

    return isMoreThanHalf;

}

// ====================方法1====================

//受快排启发，进行一轮快排，看本轮的中点是在数组的哪部分，具体分三种情况

int MoreThanHalfNum_Solution1(int* numbers, int length)

{

    if (CheckInvalidArray(numbers, length))

        return ;

    int middle = length >> ;

    int start = ;

    int end = length - ;

    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 - ;

            index = Partition(numbers, length, start, end);

        }

        else//如果index != middle，且index < middle，则在index右边

        {

            start = index + ;

            index = Partition(numbers, length, start, end);

        }

    }

    int result = numbers[middle];

    if (!CheckMoreThanHalf(numbers, length, result))//必须检查，有可能不是

        result = ;

    return result;

}

// ====================方法2====================

//这个比较复杂，就是下一值如果和当前值一致，count就+1,否则-1，如果为0，则舍弃记录当前值，改下一值，最后+1的值可能会超过一半

int MoreThanHalfNum_Solution2(int* numbers, int length)

{

    if (CheckInvalidArray(numbers, length))

        return ;

    int result = numbers[];//初试为第一个值

    int times = ;//初试为1

    for (int i = ; i < length; ++i)

    {

        if (times == )//改记录下一值

        {

            result = numbers[i];

            times = ;

        }

        else if (numbers[i] == result)

            times++;

        else

            times--;

    }

    if (!CheckMoreThanHalf(numbers, length, result))

        result = ;

    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 = ; 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[] = { , , , , , , , ,  };

    Test("Test1", numbers, sizeof(numbers) / sizeof(int), , false);

}

// 不存在出现次数超过数组长度一半的数字

void Test2()

{

    int numbers[] = { , , , , , , , ,  };

    Test("Test2", numbers, sizeof(numbers) / sizeof(int), , true);

}

// 出现次数超过数组长度一半的数字都出现在数组的前半部分

void Test3()

{

    int numbers[] = { , , , , , , , ,  };

    Test("Test3", numbers, sizeof(numbers) / sizeof(int), , false);

}

// 出现次数超过数组长度一半的数字都出现在数组的后半部分

void Test4()

{

    int numbers[] = { , , , , , , , ,  };

    Test("Test4", numbers, sizeof(numbers) / sizeof(int), , false);

}

// 输入空指针

void Test5()

{

    int numbers[] = {  };

    Test("Test5", numbers, , , false);

}

// 输入空指针

void Test6()

{

    Test("Test6", nullptr, , , true);

}

int main(int argc, char* argv[])

{

    Test1();

    Test2();

    Test3();

    Test4();

    Test5();

    Test6();

    system("pause");

    return ;

}

《剑指offer》第三十九题（数组中出现次数超过一半的数字）的相关教程结束。