找出数组中出现次数超过一半的数，现在有一个数组，已知一个数出现的次数超过了一半，请用O(n)的复杂度的算法找出这个数。

我们可以用摩尔投票算法（Boyer-Moore Voting Algorithm）解决这个问题。

假设这个数为x，每次从数组中取出两个数，如果这两个数都不等于x，则将这两个数从数组中删除；如果只有一个数等于x，则将这两个数从数组中删除，并将x出现的次数+1；如果两个数都等于x，则将这两个数从数组中删除，并将x出现的次数+2。

由于x出现的次数超过了数组长度的一半，因此最终x一定会存活下来。我们只需要再扫描一遍数组，统计x的出现次数即可。

时间复杂度：O(n)
空间复杂度：O(1)

以下是代码实现：

int findMajority(int arr[], int n) {
int x = arr[0];
int count = 0;
for (int i = 0; i < n; i++) {
if (arr[i] == x) {
count++;
} else {
count--;
}
if (count <= 0) {
x = arr[i];
count = 1;
}
}
count = 0;
for (int i = 0; i < n; i++) {
if (arr[i] == x) {
count++;
}
}
if (count > n / 2) {
return x;
} else {
return -1; //数组中不存在出现次数超过一半的数
}
}