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

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

【试题来源】未知

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

【参考代码】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
}
坚持原创技术分享,您的支持将鼓励我继续创作!