方法一：利用快排思想
如果轴值的下标正好是n/2，那么该轴值就是中位数，如果小于，说明目标数在下标的右侧，对右侧快排，如果大于，对左侧快排。最后下标等于n/2，就是目标数。
下面是比较详细的表述：
事实上可以不用对数组进行排序，或者说仅部分排序，受快速排序的partition函数的启发，我们可以利用反复调用partition函数来求的该数字。我们现在数组中随机选取一个数字，而后通过Partition函数返回该数字在数组中的索引index，如果index刚好等于n/2，则这个数字便是数组的中位数，也即是要求的数，如果index大于n/2，则中位数肯定在index的左边，在左边继续寻找即可，反之在右边寻找。这样可以只在index的一边寻找，而不用两边都排序，减少了一半排序时间。这种情况的平均时间复杂度大致为：T(n) = n+n/2+n/4+n/8+....+1，很明显当n很大时，T(n)趋近于2n，也就是说平均情况下时间复杂度为O(n),但是这种情况下，最坏的时间复杂度依然为O(n*n)，最坏情况下，index总是位于数组的最左或最右边，这样时间复杂度为T(n) = n+n-1+n-2+n-3+....+1 = n(n-1)/2，显然，时间复杂度为O(n*n)，空间复杂度为O(1)。
int MoreThanHalfNum_Solution(vector<int> numbers)以上快排参考 白话经典算法系列之六 快速排序 快速搞定
{
//vector<int> numbers1(numbers);//因为快排并没有进行完成，有的数重复存在。真tm尴尬是自己写错了
if(numbers.size()==0)
return 0;
int middle=(numbers.size())>>1;
int index=partition(numbers,0,numbers.size()-1);
int l = 0;
int r = numbers.size() - 1;
while(index!=middle)
{
if (index < middle)
{
l = index + 1;
index = partition(numbers, l, r);
}
else
{
r = index - 1;
index = partition(numbers, l, r);
}
}
int result=numbers[index];
int times=0;
for(auto z:numbers) ///
{
if(z==result)
times++;
}
if (times>numbers.size()/2)
return numbers[index];
else
return 0;
}
int partition(vector<int> &s,int l,int r)
{
int i=l;
int j=r;
int x=s[i];
while(i<j)
{
while(i<j&&s[j]>=x)
j--;
if(i<j)
{
s[i]=s[j];
i++;
}
while(i<j&&s[i]<x)
i++;
if(i<j)
{
s[j]=s[i];
j--;
}
}
s[i]=x;
return i;
}
方法二：采用阵地攻守思想
第一个数字作为第一个士兵，守阵地；count = 1； 遇到相同元素，count++; 遇到不相同元素，即为敌人，同归于尽,count--；当遇到count为0的情况，又以新的i值作为守阵地的士兵，继续下去，到最后还留在阵地上的士兵，有可能是主元素。 再加一次循环，记录这个士兵的个数看是否大于数组一般即可。
int MoreThanHalfNum_Solution(vector<int> numbers) {
int count=1;
int guard=numbers[0];
for(int i=1;i<numbers.size();i++)
{
if(count==0)
{
guard=numbers[i];
count=1;
}
else if (guard==numbers[i])
count++;
else
count--;
}
int times=0;
for(auto z:numbers)
{
if(z==guard)
times++;
}
if (times>numbers.size()/2)
return guard;
else
return 0;
}