题解 | #数组中出现次数超过一半的数字#
数组中出现次数超过一半的数字
http://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163
题意：
给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
方法一：
计数数组
思路：用一个计数数组记录每个数出现的次数。
先遍历一遍原数组，对数出现次数进行统计，并存储在数组中。
最后遍历一遍
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
int cnt[10005];//计数数组
int n=numbers.size();
for(int i=0;i<n;i++){//计数
cnt[numbers[i]]++;
}
for(int i=0;i<=10000;i++){
if(cnt[i]>n/2)//如果某个数出现的次数大于数组长度的一半，则返回该数
return i;
}
return 0;
}
};
时间复杂度：%2Cn%E6%98%AF%E6%95%B0%E7%BB%84%E7%9A%84%E5%A4%A7%E5%B0%8F%2Cm%E6%98%AF%E5%85%83%E7%B4%A0%E5%80%BC%E7%9A%84%E6%9C%80%E5%A4%A7%E5%80%BC)
空间复杂度：%EF%BC%8Cm%E6%98%AF%E5%85%83%E7%B4%A0%E5%80%BC%E7%9A%84%E6%9C%80%E5%A4%A7%E5%80%BC%E3%80%82)
方法二：
思维
思路：思想类似一换一。
因为我们要的答案数值的个数是超过数组大小的一半，因此当答案数值与其他数一对一的消去后（即一换一），还会剩余答案数值。将每个数因为数值不同，而规定着属于不同的阵营。当一个数遇到不等于本身阵营（即数值不等于自身）时，就一对一消去，最后剩的数肯定是我们所要的答案数值。
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
int n=numbers.size();
int x,cnt=0;
for(int i=0;i<n;i++){
if(cnt==0){//当cnt==0,x设置为新值，即新建阵营
x=numbers[i];
cnt++;
}else{
if(x==numbers[i]){//阵营相同，自增
cnt++;
}else{//阵营不同，自减
cnt--;
}
}
}
return x;
}
};
时间复杂度：%2Cn%E6%98%AF%E6%95%B0%E7%BB%84%E7%9A%84%E5%A4%A7%E5%B0%8F%E3%80%82)
空间复杂度：%EF%BC%8C%E4%B8%8D%E9%9C%80%E9%A2%9D%E5%A4%96%E5%AD%98%E5%82%A8)
投递快手等公司10个岗位