剑指Offer-29-数组出现次数超过一半的数字-基于Partition函数的O（n）算法

如果把这个数组排序，那么排序之后位于数组中间的数字一定就是出现次数超过数组长度一半的数字。也就是说，这个数字就是是统计学中的中位数。
在随机快速排序算法中，我们现在数组中随机选择一个数字，然后调整数组中数字的顺序，使得比选中数字小的数字都排在它的左边，比选中的数字大的数字都排在它的右边。如果这个选中的数字的下标正好是n/2（中位数），那么这个数字就是待定的出现次数超过一半的数字的候选（因为有一种可能就是这个数组没有出现次数超过一半的数字）。

#include <iostream>
using namespace std;

//用于标记输入的数组是否含有超过数组长度一半的元素
bool g_bInputInvalid = false;

//调用Partition(a，low，high)时，对a[low..high]做划分，
//并返回基准记录的位置
int Partition(int a[], int low, int high) {
//以第一个元素作为基准值
//比pivot值小的元素放在数组的左边，比pivot值大的元素放在数组右边
int pivot = a[low];

//从区间两端交替向中间扫描，直至low=high为止
while (low < high) {
while (low < high && a[high] >= pivot)//pivot相当于在位置low上
            high--;//从右向左扫描，查找第1个关键字小于pivot.key的记录a[high]
if (low < high)//表示找到的a[high]的关键字<pivot
            Swap(&a[low++], &a[high]);//相当于交换a[low]和a[high]，交换后low指针加1

while (low < high && a[low] <= pivot)//pivot相当于在位置high上
            low++;//从左向右扫描，查找第1个关键字大于pivot.key的记录a[low]
if (low < high)//表示找到的a[low]的关键字>pivot
            Swap(&a[low], &a[high--]);//相当于交换a[low]和a[high]，交换后high指针减1
    }
    a[low] = pivot;
//基准记录已被最后定位
return low;
}

//查找出现次数超过一半的数字
int MorethanHalfNum(int* a, int length) {
if (a == NULL || length <= 0) {
        g_bInputInvalid = false;
return -1;
    }
int mid = length/2;
int low = 0,high = length-1;
int index = Partition(a,low,high);
while(index != mid) {
if(index < mid) {
            low = index+1;
index = Partition(a,low,high);
        }
else {
            high = index-1;
index = Partition(a,low,high);
        }
    }
//确定候选元素是否符合条件
int count = 0;
for (int i = 0; i < length; i++) {
if (a[i] == a[index]) {
count++;
        }
    }
if (count >= length / 2) {
        g_bInputInvalid = true;
return a[index];
    } else {
        g_bInputInvalid = false;
return -1;
    }
}