2021-06-18发表2021-06-18更新刷题6 分钟读完 (大约936个字)

剑指offer-39

剑指 Offer 39. 数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例

1 2	输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2

官方题解

方法四：分治

如果数 a 是数组 nums 的众数，如果我们将 nums 分成两部分，那么 a 必定是至少一部分的众数。

我们可以使用反证法来证明这个结论。假设 a 既不是左半部分的众数，也不是右半部分的众数，那么 a 出现的次数少于 $\frac{l}{2} + \frac{r}{2}$ 次，其中 $l$ 和 $r$ 分别是左半部分和右半部分的长度。

由于 $\frac{l}{2} + \frac{r}{2} \leq \frac{l+r}{2}$，说明 a 也不是数组 nums 的众数，因此出现了矛盾。所以这个结论是正确的。

这样以来，我们就可以使用分治法解决这个问题：将数组分成左右两部分，分别求出左半部分的众数 a1 以及右半部分的众数 a2，随后在 a1 和 a2 中选出正确的众数。

算法

我们使用经典的分治算法递归求解，直到所有的子问题都是长度为 1 的数组。长度为 1 的子数组中唯一的数显然是众数，直接返回即可。

如果回溯后某区间的长度大于 1，我们必须将左右子区间的值合并。

如果它们的众数相同，那么显然这一段区间的众数是它们相同的值。

否则，我们需要比较两个众数在整个区间内出现的次数来决定该区间的众数。

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        def majority_element_rec(lo,hi) ->int:
            if lo == hi:
                return nums[lo]
            
            # 划分左右区间
            mid = (hi-lo) // 2 +lo
            left = majority_element_rec(lo,mid)
            right = majority_element_rec(mid+1,hi)

            # 如果两部分在众数上一致，则返回
            if left == right:
                return left

            # 否则，比较两个里面谁多
            left_count = sum(1 for i in range(lo, hi + 1) if nums[i] == left)
            right_count = sum(1 for i in range(lo, hi + 1) if nums[i] == right)
            
            res = left if left_count > right_count else right
            print(res)
            return res
        return majority_element_rec(0, len(nums) - 1)

方法五：Boyer-Moore 投票算法

思路

如果我们把众数记为 +1，把其他数记为 −1，将它们全部加起来，显然和大于 0，从结果本身我们可以看出众数比其他数多。

极限一换一

算法

Boyer-Moore 算法的本质和方法四中的分治十分类似。我们首先给出 Boyer-Moore 算法的详细步骤：

我们维护一个候选众数 candidate 和它出现的次数 count。初始时 candidate 可以为任意值，count 为 0；
我们遍历数组 nums 中的所有元素，对于每个元素 x，在判断 x 之前，如果 count 的值为 0，我们先将 x 的值赋予 candidate，随后我们判断 x：
- 如果 x 与 candidate 相等，那么计数器 count 的值增加 1；
- 如果 x 与 candidate 不等，那么计数器 count 的值减少 1。
在遍历完成后，candidate 即为整个数组的众数。

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = 0
        candidate = None

        for num in nums:
            # 初始状态
            if count == 0:
                candidate = num
            
            count += (1 if num == candidate else -1)

        return candidate