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

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

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

思路：一个数字在数组中出现次数超过了一半，则排序后，位于数组中间的数字一定就是该出现次数超过了长度一半的数字（，也即是说，这个数字就是统计学上的中位数。事实上可以不用对数组进行排序，或者说仅部分排序，受快速排序的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");
}

本文永久更新链接地址：