剑指offer - 数组中出现次数超过一半的数字

题目

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

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

分析

• 思路1

很容易想到要是这个数组是排序的数组就好了，如果是排序的数组，那么就能很容易统计出每个数字出现的次数。因此需要先排序，排序时间的复杂度为O(nlogn)

int MoreThanHalfNumber(vector<int> numbers) {
     // 因为用到了sort，时间复杂度O(NlogN)，并非最优
    if (numbers.empty()) return 0;

    // 排序，取数组中间那个数
    sort(numbers.begin(), numbers.end());
    int middle = numbers[numbers.size() / 2];

    int count = 0;
    for (int i = 0; i < numbers.size(); ++i) {
        if (numbers[i] == middle) ++count;
    }

    return (count > numbers.size()/2) ? middle : 0;
}

• 思路2

基于 Partition 函数的 O（n）算法

数组的特性：数组中有一个数字出现的次数超过了数组长度的一半。如果把这个数组排序，那么排序之后位于数组中间的数字一定就是那个出现次数超过数组长度一半的数字。也就是说，这个数字就是统计学上的中位数，即长度为n的数组中第n/2大的数字。

在随机快速排序算法中，先在数组中随机选择一个数字，然后调整数组中数字的顺序，使得比选中的数字小的数字都排在它的左边，比选中数字大的数字都排在它的右边。

如果这个选中的数字的下标刚好是n/2，那么这个数字就是数组的中位数；如果它的下标大于n/2，那么中位数应该位于它的左边，我们可以接着在它的左边部分的数组中查找；如果它的下标小于n/2，那么中位数应该位于它的右边，我们可以接着在它的右边部分的数组中查找。这是应该典型的递归过程

int partition(vector<int> &input,int low,int high) {
    int pivotkey=input[low];   //pivot:枢纽,这里的pivotkey也可以是[low,high]区间一个随机数
    while(low<high) {
        while(low<high&&pivotkey<=input[high])
            high--;
        input[low] = input[high];

        while(low<high&&pivotkey>=input[low])
            low++;
        input[high] = input[low];
    }
    input[low] = pivotkey;
    return low;
}

// 检查result的值的个数是否大于整个数组的一半
bool CheckMoreThanHAlf(vector<int> numbers,int length,int result) {
    int times=0;
    for(int i=0;i<length;++i){
        if(numbers[i]==result)
            times++;
    }
    bool isMoreThanHalf=true;
    if(times*2<=length)
        isMoreThanHalf=false;
    return isMoreThanHalf;
}

int MoreThanHalfNum_Solution(vector<int> numbers) {
    int length = numbers.size();
    if(numbers.empty()||length<0)
        return 0;
    int middle=length>>1;
    int start=0;
    int end=length-1;
    int index=partition(numbers,start,end);
    while(index!=middle) {
        if(index>middle) {
            end=index-1;
            index=partition(numbers,start,end);
        } else {
            start=index+1;
            index=partition(numbers,start,end);
        }
    }
    int result=numbers[middle];

    //这里的只是得到了第middle=n/2大的数字，但总个体是否超过一段还需要判断
    if(!CheckMoreThanHAlf(numbers,length,result))
        return 0;

    return result;
}

• 思路3

如果有符合条件的数字，则它出现的次数比其他所有数字出现的次数和还要多。在遍历数组时保存两个值：一是数组中一个数字，一是次数。遍历下一个数字时，若它与之前保存的数字相同，则次数加1，否则次数减1；若次数为0，则保存下一个数字，并将次数置为1。遍历结束后，所保存的数字即为所求。然后再判断它是否符合条件即可。

#include <iostream>
using namespace std;

bool inputInvalid = false;
bool CheckInvalidArray(int *numbers, int length);
bool CheckMoreThanHalf(int *numbers, int length, int number);

// 确认输入数组是否有值
bool CheckInvalidArray(int *numbers, int length) {
    inputInvalid = false;
    if (numbers == nullptr || 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++;
    }

    // 如果times的2倍大于length，即number为查找值
    bool isMoreThanHalf = true;
    if (times * 2 <= length) {
        inputInvalid = true;
        isMoreThanHalf = false;
    }

    return isMoreThanHalf;
}

int MoreThanHalfNum(int *numbers, int length) {
    if (CheckInvalidArray(numbers, length))
        return 0;

    // 获取数组第一个元素的值
    int result = numbers[0];
    // 出现次数设置为1
    int times = 1;
    // 遍历数组
    for (int i = 1; i < length; ++i) {
        if (times == 0) { // 出现次数为0，将当前值作为查找值，继续遍历
            result = numbers[i];
            times = 1;
        } else if (numbers[i] == result) { // 数组中当前值和查找结果值相等
            times++; // 出现次数加1
        } else {
            times--; // 出现次数减1
        }
    }

    // 确认查找值
    if (!CheckMoreThanHalf(numbers, length, result))
        return 0;

    return result;
}

• 思路4

考虑用哈希，key保存数组元素，value保存出现的次数，这样在遍历O(n)能做出key-value的映射，再用O(k)(k为需要的槽的个数)可以找出出现次数超过一半的key。

int MoreThanHalfNum_Solution3(vector<int> numbers) {
    map<int,int> numbersMap;
    for(int i=0;i<numbers.size();i++){
        numbersMap[numbers[i]]+=1;
    }
    
    int max = numbers.size()/2;
    int number = 0;
    for(map<int,int>::iterator it=numbersMap.begin(); it!=numbersMap.end(); it++){
        if(max<(it->second)){
            number=it->first;
        }
    }
    return number;
}

参考

《剑指offer》
数组中出现次数超过一半的数字