快乐的LeetCode --- 961. 重复 N 次的元素

男娘i 2023-02-14 01:42 3阅读 0赞

**往期回顾：**

[快乐的LeetCode — 287. 寻找重复数][LeetCode _ 287.]

**题目描述：**

在大小为 2N 的数组 A 中有 N+1 个不同的元素，其中有一个元素重复了 N 次。返回重复了 N 次的那个元素。

**示例 1：**

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

**示例 2：**

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

**示例 3：**

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

--------------------

**解题思路1:**

数组的长度为2N，重复了N次的元素，肯定是出现次数最多的那个，所以直接使用collections包中的Counter模块完成即可。

--------------------

**代码1：**

from collections import Counter
    class Solution(object):
        def repeatedNTimes(self, A):
            N = len(A) // 2
            return Counter(A).most_common(1)[0][0]

--------------------

**解题思路2:**

找重复数字的一种典型方法就是：(原始数组 - 求集合后的差值) / 长度差

--------------------

**代码2：**

class Solution(object):
        def repeatedNTimes(self, A):
            return abs(sum(A)-sum(set(A)))/(len(A)-len(set(A)))

--------------------

**解题思路3:**

通过设置最大零数组，然后逐个遍历原有数组，当元素首次出现时，加1。这样，当满足出现的次数时，我们即可找出重复元素。

--------------------

**代码3：**

class Solution(object):
        def repeatedNTimes(self, A):
            bitmap = [0 for _ in range(max(len(A), max(A)+1))]
            for num in A:
                if bitmap[num] == (len(A) // 2)-1:
                    return num
                else:
                    bitmap[num] += 1

--------------------

**题目来源：**

[https://leetcode-cn.com/problems/n-repeated-element-in-size-2n-array][https_leetcode-cn.com_problems_n-repeated-element-in-size-2n-array]

[LeetCode _ 287.]: https://blog.csdn.net/weixin_43283397/article/details/106438688
[https_leetcode-cn.com_problems_n-repeated-element-in-size-2n-array]: https://leetcode-cn.com/problems/n-repeated-element-in-size-2n-array