数组中出现次数超过一半的数字

题目

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组 {1, 2, 3, 2, 2, 2, 5, 4, 2} 。由于数字 2 在数组中出现了5次， 超过数组长度的一半，因此输出2。

解法一

数组中有一个数字出现的次数超过了数组长度的一半，如果把这个数组排序，那么排序之后位于数组中间的数字就是出现次数超过数组长度一半的数字。这个数就是统计学里的中位数。

即长度为n的数组中第n/2大的数字。可以用时间复杂度为 O(n) 的算法得到数组中任意第k大的数字。

这里可以利用快速排序中的Partition函数来完成这个功能。

代码（cpp）

void Swap(int *a, int *b)
{
    int t = *a;
    *a = *b;
    *b = t;
}
//生成随机数
int RandomInRange(int start, int end)
{
    srand( (unsigned int)time(0) );
    return start + rand() % (end - start);
}
//选中一个数字，比选择数字小的数字移到数组的左边，比选择的数组大的数字移到数组的右边
int Partition(int data[], int length, int start, int end)
{
    if(data == NULL || length <= 0 || start < 0 || end >= length)
    {
        return -1;
    }
    int index = RandomInRange(start, end);//生成一个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;
}

//检测数组是否无效，无效返回true
bool CheckInvalidArray(int* numbers, int length)
{
    bool InputInvalid = false;
    if(numbers == NULL || length <= 0)
        InputInvalid = true;
    return InputInvalid;
}

//检查是否超过了数组中的一半
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 )
        {
            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;
}

解法二

数组中有一个数字出现的次数超过数组长度的一半，也就是说比其他数字出现的次数和还要多。

遍历数组的时候保存两个值：一个是数组中的一个数字，一个是次数。当遍历下一个数字的时候，如果下一个数字和我们之前保存的数字相同则次数加1；不同，则次数减1。如果次数为零，我们保存下一个数字，并且次数设置为1.

时间复杂度为O(n)。

代码（cpp）

int MoreThanHalfNum(int* numbers, int length)
{
  	//检测数组是否有效
    if(CheckInvalidArray(numbers, length))
        return 0;
    int result = numbers[0];
    int times = 1;
    for(int i = 1; i < length; i++)
    {
        if(times == 0){
            result = numbers[i];
            times = 1;
        }
        else if(result == numbers[i])
        {
            times++;
        }
        else
        {
            times--;
        }
    }

    if(!CheckMoreThanHalf(numbers, length, result))
        result = 0;
    return result;
}