数组中有一个数字出现的次数超过数组长度的一半，请找出这个数 字。例如输入一个长度为 9 的数组{1,2,3,2,2,2,5,4,2}。由于数字 2 在 数组中出现了 5 次，超过数组长度的一半，因此输出 2。如果不存在 则输出 0。 要求：时间复杂度不能超过 O(n)

这道题可以使用摩尔投票法（Moore Voting）来解决，时间复杂度为 O(n)。

算法步骤如下：

1. 初始化候选数为数组的第一个数，计数器为 1。
2. 从数组的第二个数开始遍历，如果当前数等于候选数，则计数器加 1，否则计数器减 1。
3. 如果计数器为 0，则将候选数更换为当前数，计数器重置为 1。
4. 遍历完成后，候选数即为出现次数超过数组长度一半的数，但还需要再遍历一遍数组，统计该数出现的次数，判断其是否真的出现次数超过了数组长度的一半。

以下是代码实现：

int MoreThanHalfNum_Solution(vector<int>& nums) {
    int candidate = nums[0];
    int count = 1;
    for (int i = 1; i < nums.size(); i++) {
        if (nums[i] == candidate) {
            count++;
        } else {
            count--;
        }
        if (count == 0) {
            candidate = nums[i];
            count = 1;
        }
    }
    int cnt = 0;
    for (int num : nums) {
        if (num == candidate) {
            cnt++;
        }
    }
    return cnt > nums.size() / 2 ? candidate : 0;
}