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

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

解题思路

• 排序后遍历（相当于简化后的暴力）O(logn)
• 根据数组特点，相当于寻找数组的中位数，O(n)

上代码（C++香）

法一：排序后遍历（相当于简化后的暴力）

#include <iostream>
#include <algorithm>
#include <math.h>
#include <cstring>
#include "ListNode.h"
#include "TreeNode.h"
#include "Graph.h"
using namespace std;

#define MAXNUM 100010
#define DRIFT 1001

void mySwap(vector<int> &num, int i, int j){
    int temp = num[j];
    num[j] = num[i];
    num[i] = temp;
}

int myPartition(vector<int> &num, int low, int high){
    int pivot = num[low];
    while(low < high){
        // 将右边比pivot小的放到左边
        while(low < high && num[high] >= pivot)
            high--;
        mySwap(num, low, high);
        while(low < high && num[low] <= pivot)
            low++;
        mySwap(num, low, high);
    }
    return low;
}

// 快排
void QSort(vector<int> &num, int low, int high){
    if(low >= high)
        return ;
    int pivot = myPartition(num, low, high);
    QSort(num, low, pivot - 1);
    QSort(num, pivot + 1, high);
}

// 已排序的数组
int MoreThanHalfNum_Solution(vector<int> numbers) {

    // 先排序
    QSort(numbers, 0, numbers.size() - 1);
    for(int i = 0; i < numbers.size(); i++)
        cout<<numbers[i];
    cout<<endl;
    // 数组的一半
    int halfNum = numbers.size() / 2;
    for(int i = 0; i <= halfNum; i++){
        int sum = 0;
        for(; sum < halfNum + 1; sum++)
            if(numbers[i + sum] != numbers[i])
                break;
        if(sum == halfNum + 1){
            return numbers[i];
            break;
        }
    }
    return 0;
}

int main()
{
    vector<int> numbers;
    numbers.push_back(1);
    numbers.push_back(2);
    numbers.push_back(3);
    numbers.push_back(2);
    numbers.push_back(2);
    numbers.push_back(2);
    numbers.push_back(5);
    numbers.push_back(4);
    numbers.push_back(2);
    cout<<MoreThanHalfNum_Solution(numbers);
    return 0;
}

法二：借助快排的Partition思想

  得到的pivot值，左边的值都比num[pivot]小，右边的值都比num[pivot]大，如果pivot等于middle，那么这个位置正好就是中位数（理解为中间那个数更好）的位置。

  其实剑指offer书本上的介绍是有错误的，真正的中位数定义为：

• 如果数组长度为奇数，那么中位数就是这个数组排序后的中间那个位置的数
• 如果数组长度为偶数，那么中位数就是这个数组排序后的中间两个数的平均数

void mySwap(vector<int> &num, int i, int j){
    int temp = num[j];
    num[j] = num[i];
    num[i] = temp;
}

int myPartition(vector<int> &num, int low, int high){
    int pivot = num[low];
    while(low < high){
        // 将右边比pivot小的放到左边
        while(low < high && num[high] >= pivot)
            high--;
        mySwap(num, low, high);
        while(low < high && num[low] <= pivot)
            low++;
        mySwap(num, low, high);
    }
    return low;
}

int MoreThanHalfNum_Solution(vector<int> numbers) {

    int middle = (numbers.size()) >> 1;
    int low = 0;
    int high = numbers.size() - 1;
    int pivot = myPartition(numbers, low, high);
    while(pivot != middle){
        // 中位数在左边
        if(pivot > middle){
            high = pivot - 1;
            pivot = myPartition(numbers, low, high);
        }
        // 中位数在右边
        else{
            low = pivot + 1;
            pivot = myPartition(numbers, low, high);
        }
    }
    
    int times = 0;
    for(int i = 0; i < numbers.size(); i++){
        if(numbers[i] == numbers[pivot])
            times++;
    }
    if(times * 2 > numbers.size())
        return numbers[pivot];
    
    return 0;
}