分析：若有超过一半的数，排序之后，数组中的中位数一定是该数字。
可用方法：

1. sort函数实现快速排序（快速排序时间复杂度O(NlogN))
   2.用map储存数字和出现次数的对应关系（用空间复杂度弥补时间复杂度）
   3.Partition(numbers , begin , end)函数（返回一个数在这个数组中处于第几个位置），递归使用得到中位数。

int Partition(vector<int> numbers,int begin,int end){
    if(begin>end){
        return begin;
    }
    int key = numbers[begin];
    while(begin<end){
        while(begin<end&&numbers[end]>=key){
            end--;
        }
        numbers[begin]=numbers[end];
        while(begin<end&&numbers[begin]<=key){
            begin++;
        }
        numbers[end]=numbers[begin];
    }
    numbers[begin]=key;
    return begin;
}

4. 保存第一个数，遍历数组，如果和第一个相同则加一，如果不同则减一，若次数为0，需要保存下一个值，由于我们要找的数字出现的次数比其他所有数字出现次数之和还要多，那么要找的数字肯定是最后一次把次数设为1对应的数字。

总结：1、3方法改变了数组的顺序，2、4方法未改变数组顺序，2、3、4在时间复杂度上为O(logN)，2牺牲了空间复杂度来节省时间复杂度。

Partition也可以实现快速排序

void quickSort(vector<int> &nums, int begin, int end)
{

    if (begin >= end) return;

    int index = partition(nums, begin, end);
    if (index>begin)
        quickSort(nums, begin, index-1);
    if (index<end)
        quickSort(nums, index+1, end);
}