【Leetcode Daily】961在长度2N的数组中找出重复N次的元素

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个数组，长度 2n，现在其中有一个数字重复 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/?envType=daily-question&envId=2026-01-02

• 但是这种解法的空间复杂度是 O(n)，有一种 O(1) 的解决方案叫做摩尔投票。具体怎么做，后面再说，今天先到这里：）

• 这里是睡完午觉的陆爻齐，补上空间复杂度 O(1) 的解决方案，就是参照 【Leetcode Daily】169多数元素 的多数投票法，但本题的这个元素并非严格大于，需要做一点改变，也就是剔除第一个元素。

• 具体的说，如果第一个元素在后面有重复的，就当做答案，如果这个不是答案，那么剩下的元素中，答案的个数严格大于剩下的数字，就能使用多数投票法了。

代码解答（强烈建议自行解答后再看）

• 参考题解

class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        x, hp = nums[0], 1
        for num in nums[1:]:
            if num == x:
                return x
            
            if hp == 0:
                x = num
                hp = 1
            else:
                hp += 1 if num == x else -1

        return x

        rec = set()
        for num in nums:
            if num in rec:
                return num
            rec.add(num)