LeetCode-961:重复 N 次的元素

重复 N 次的元素 - 力扣(LeetCode)

1. 遍历计数

关键算法

  • 利用collections.Counter类,输出most_common为1的元素即可(LeetCode已经导入了部分Python标准库)

代码实现

时间复杂度:O(n),空间复杂度:O(n)

class Solution:
    def repeatedNTimes(self, A: List[int]) -> int:
        return collections.Counter(A).most_common(1)[0][0]

2. 鸡兔同笼

关键算法

  • 原列表求和减去原列表去重求和的差就是N个所求元素的值

代码实现

时间复杂度:O(n),空间复杂度:O(n)

class Solution:
    def repeatedNTimes(self, A: List[int]) -> int:
        return (sum(A)-sum(set(A)))//(len(A)//2-1)

3. 寻找重复值

关键算法

  • 利用集合寻找重复值

代码实现

class Solution:
    def repeatedNTimes(self, A: List[int]) -> int:
        s = set()
        for i in A:
            if i in s:
                return i
            s.add(i)