数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为 9的数组［1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出 2。如果不存在则输出0。写出实现代码以及算法复杂度。（要求用尽可能低的时间和空间复杂度） a ．设计算法思路及步骤； b ．实现算法伪代码； c ．给出算法时间复杂度。

a. 算法思路：

设目标数字为target，遍历数组，如果当前数字与target相同，则计数器加1，否则计数器减1。当计数器为0时，将target更换为当前数字。遍历结束后，如果target的出现次数超过数组长度的一半，则返回target，否则返回0。

b. 算法伪代码：

function findMajorityElement(nums: array) -> int:
    target = nums[0]
    count = 1
    for i in range(1, len(nums)):
        if nums[i] == target:
            count += 1
        else:
            count -= 1
            if count == 0:
                target = nums[i]
                count = 1

    # 验证target是否为出现次数超过数组长度一半的数字
    count = 0
    for num in nums:
        if num == target:
            count += 1

    if count > len(nums) / 2:
        return target
    else:
        return 0

c. 算法的时间复杂度为 O(N)，其中遍历数组需要 O(N) 的时间复杂度，验证target是否为出现次数超过数组长度一半的数字需要 O(N) 的时间复杂度，因此总时间复杂度为 O(N)。空间复杂度为 O(1)，只需要常数级别的变量来存储target和count。