题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
解法1：
需要O(n)时间，（剑指解法2）
1)它比较的是两两相临近的的数组是否相等，相等则计数1，同时参与比较的这个数num保持不变参与下一次的比较；
2）否则计数为0时，num重新取值；因为条件是：出现的次数大于数组长度的一半，为此肯定会出现相邻两个数重复的情况；
3）最后只要判断最后num的数值就是出现的次数大于数组长度的一半的数；
考虑的特殊条件是：数组长度为0；或者出现的次数小于数组长度的一半
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers)
{
int n = numbers.size();//数组的长度
if (n == 0) return 0;
int num = numbers[0], count = 1;
for (int i = 1; i < n; i++)
{
if (numbers[i] == num)
count++;
else count--;
if (count == 0)
{
num = numbers[i];
count = 1;
}
}
// 判断是否有效，满足出现的次数超过数组的一半吗
count = 0;
for (int i = 0; i < n; i++)
{
if (numbers[i] == num) count++;
}
if (count * 2 > n) return num;
return 0;
}
};
解法2：C++自带的快速排序，并取中间的值作为结果
// 该方法取排序数组中间的值，即是该数字出现的次数超过数组长度的一半，也称为中位数
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers)
{
// 因为用到了sort，时间复杂度O(NlogN)，并非最优
if(numbers.empty()) return 0;
// C++ 内的sort默认为快排参考 https://www.cnblogs.com/jjzzx/p/5122381.html
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;
}
};
