经典面试题16 - 数组中出现次数超过一半的数字
2017-03-12 本文已影响120人
豆志昂扬
问题
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
例如： 输入一个长度为7的数组,
{1,2,2,2,5,4,2}
由于数字2在数组中出现了4次，超过数组长度的一半，因此输出2。如果不存在则输出0。
解答
首先说这是一道很经典的面试题，很多互联网公司都曾经采用过这个题目。
下面是对该题的分析思路：
-
如果没有时间复杂度的要求， 我们可以对数组进行排序，排序后的数组，那么我们只要遍历一次就可以统计出每个数字出现的次数，这样也就能找出符合要求的数字。按照这个思路的时间复杂度是O(nlogn)， 其中排序的时间复杂度是O(nlogn)，遍历的时间复杂度O(n)。
-
另一个思路是我们可以创建一个哈希表来消除排序的时间。哈希表的键值为数组中的数字，值为该数字对应的次数。有了这个哈希表之后，我们只需要遍历数组中的每个数字，找到它在哈希表中对应的位置并增加它出现的次数。这种哈希表的方法在数组的所有数字都在一个比较窄的范围内的时候很有效。
-
最佳思路：数组中有一个数字出现的次数超过数组长度的一半，也就是说它出现的次数比其他所有数字出现次数的和还要多。
因此我们可以考虑在遍历数组的时候保存两个值：一个是数组中的一个数字，一个是次数。当我们遍历到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，则次数加1；如果下一个数字和我们之前保存的数字不同，则次数减1。
如果次数为0，我们需要保存下一个数字，并把次数置1。因为次数为0，表示前面是字符串计数抵消为0。
//Java源码
public int MoreThanHalfNum_Solution(int [] numbers) {
int maxNum = 0;
if(numbers.length==0)
return maxNum;
maxNum = numbers[0];
int numCount = 1;
for(int i=1;i<numbers.length-1;i++){
if(numbers[i] == maxNum){
numCount++;
}else{
numCount--;
if(numCount == 0){
numCount = 1;
maxNum = numbers[i];
}
}
}
int total = 0;
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] == maxNum) total++;
}
if (total * 2 <= numbers.length) {
return 0;
}
else return maxNum ;
}
上述源码可以在 这里 调试
