E961.在长度 2N 的数组中找出重复 N次的元素

Boyer-Moore, https://leetcode.cn/problems/n-repeated-element-in-size-2n-array/

给你一个整数数组 nums ，该数组具有以下属性：

• nums.length == 2 * n.
• nums 包含 n + 1 个 不同的 元素
• nums 中恰有一个元素重复 n 次

找出并返回重复了 n 次的那个元素。

示例 1：

输入：nums = [1,2,3,3]
输出：3

示例 2：

输入：nums = [2,1,2,5,3,2]
输出：2

示例 3：

输入：nums = [5,1,5,2,5,3,5,4]
输出：5

提示：

• 2 <= n <= 5000
• nums.length == 2 * n
• 0 <= nums[i] <= 10^4
• nums 由 n + 1 个 不同的 元素组成，且其中一个元素恰好重复 n 次

class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        nums.sort()
        ans = nums[0]
        for n in nums[1:]:
            if ans == n:
                return ans
            else:
                ans = n

【灵茶山艾府】https://leetcode.cn/problems/n-repeated-element-in-size-2n-array/solutions/3870905/si-chong-fang-fa-ha-xi-ji-he-mo-er-tou-p-f95m/

摩尔投票，先完成169题目，再来这个题目。

为了让出现 n 次的那个数变成绝对众数，我们可以分类讨论：

如果 nums[0] 在下标 [1,n−1] 中出现过，那么返回 nums[0]。 否则，去掉 nums[0]，剩下 2n−1 个数，出现次数为 n 的那个数变成绝对众数，可以用 169 题的算法解决。 这两件事情可以在同一个循环中完成。

class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        ans = hp = 0
        for x in nums[1:]:  # 也可以写 for i in range(1, len(nums)) 避免切片
            if x == nums[0]:
                return x
            if hp == 0:  # x 是初始擂主，生命值为 1
                ans, hp = x, 1
            else:  # 比武，同门加血，否则扣血
                hp += 1 if x == ans else -1
        return ans