c++分治法求数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

解法一：排序法

先将数组排序，由于该数字出现的次数超过数组长度的一半，所以排序后中间的数一定是该数字。

时间复杂度：O(nlogn)

解法二：哈希表法

遍历数组，将每个数字出现的次数存入哈希表中，最后遍历哈希表找到出现次数超过数组长度一半的数字。

时间复杂度：O(n)，但需要额外的空间来存储哈希表。

解法三：摩尔投票法

由于该数字出现的次数超过数组长度的一半，所以可以使用一个计数器和一个候选数字，遍历数组，如果当前数字与候选数字相同，则计数器加1，否则计数器减1，如果计数器为0，则更新候选数字为当前数字。最后剩下的候选数字即为结果。

时间复杂度：O(n)

以下是摩尔投票法的Python代码实现：

def majorityElement(nums):
count = 0
candidate = None
for num in nums:
if count == 0:
candidate = num
count += (1 if num == candidate else -1)
return candidate