# 【IT笔试面试题整理】数组中出现次数超过一半的数字

- URL: https://www.yidoo.xyz/appears-more-than-half-of-the-numbers-in-the-array
- 作者: 核动力蜗牛
- 发布时间: 2012-10-05
- 更新时间: 2012-10-05
- 分类: 面试题整理
- 标签: 面试题

【试题描述】数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

【试题来源】未知

【试题分析】时间复杂度O(n),空间复杂度O(1)

【参考代码】

``` cpp 
int findMoreThanHalf(int array[], int n) {

	if(array == NULL || n <= 0) {
		throw ("Invalid input.");
	}

	int num = array[0];
	int times = 1;

	for(int i = 1; i < n; i++) {
		if(array[i] == num) {
			++times;
		} else {
			--times;
			if(times == 0) {
				num = array[i];
				times = 1;
			}
		}
	}

	return num;
}
```