快乐的LeetCode --- 287. 寻找重复数

题目描述：

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

示例 1:

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

示例 2:

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

---

解题思路1:

由于题目假设只有一个重复的整数，因此使用collections包中的Counter模块之后，出现的第一位就是次数最多的元素。

---

代码1：

from collections import Counter
class Solution(object):
    def findDuplicate(self, nums):
        return Counter(nums).most_common(1)[0][0]

---

解题思路2:

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

---

代码2：

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

---

解题思路3:

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

---

代码3：

class Solution:
    def findDuplicate(self, nums):
        bitmap = [0 for _ in range(max(len(nums), max(nums)+1))]
        for num in nums:
            if bitmap[num] == 1:
                return num
            else:
                bitmap[num] = 1

---

题目来源：

https://leetcode-cn.com/problems/find-the-duplicate-number