LeetCode怎么求数组中出现次数超过一半的数字

问题引言：

给定一个非空整数数组，其中存在一个数字的出现次数超过数组长度的一半。我们需要设计一个算法，找出这个数字并返回。

解决方案：

为了找到数组中出现次数超过一半的数字，我们可以利用"摩尔投票算法"（Boyer-Moore Voting Algorithm）。这个算法的基本思想是假设数组中的一个元素为候选数字，然后进行遍历，对于每个数字，我们将候选数字与当前数字进行比较，如果相同则计数器加1，不同则计数器减1。当计数器变为0时，我们选择当前数字作为新的候选数字，并且重置计数器为1。由于候选数字的出现次数超过一半，所以最终候选数字一定是我们要找的数字。

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

以上是使用Python编写的摩尔投票算法的实现代码。我们首先初始化计数器(count)为0，并设置候选数字(candidate)为None。然后对数组进行遍历，对于每个数字，我们进行如下操作：

• 若计数器(count)为0，则将当前数字设置为候选数字，并将计数器(count)设为1。
• 若当前数字和候选数字相等，则计数器(count)加1。
• 若当前数字和候选数字不等，则计数器(count)减1。

最终，候选数字即为所求的出现次数超过一半的数字，我们将其作为结果返回。

总结：

本解决方案使用了摩尔投票算法来找出数组中出现次数超过一半的数字。该算法的时间复杂度为O(n)，其中n是数组的长度。通过遍历数组一次，我们可以在常数空间内找到所需的结果。这个算法在处理类似问题时非常高效。