给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
示例 1:
输入: [1,3,4,2,2]
输出: 2
示例 2:
输入: [3,1,3,4,2]
输出: 3
说明：
不能更改原数组（假设数组是只读的）。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。
数组中只有一个重复的数字，但它可能不止重复出现一次。
解题思路：
首先，我们人类的思维是从前往后数，每次在前面找有没有重复的，找到就停止了。但是这样时间复杂度是O(n2)，因为每一次都需要从头遍历到当前位置。
然后我想到了使用集合，分别对nums和nums的集合求和再相减，这样就可以找到重复的值了，又因为重复的数字可能不止一个，所以还要除以nums和nums的集合的长度的差值。
代码如下：
class Solution:
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
a=set(nums)
coun=len(nums)-len(a)
return int((sum(nums)-sum(a))/coun)
代码很简单，跑的也很快，排在第二条柱子上。
但是，我在写这篇博客时，突然想到python的列表转集合会去掉重复的值，那这个值不就是我们需要的么？还要后面的求和相减相除的那些干什么？还有，python是怎样实现列表转集合的？它是不是每添一个数也要遍历一下，看是不是有重复的？
我们一直使用着python便利的内置库，内置方法，但有没有思考过这些方法的代码实现是怎么样的？虽然说python本身就运行效率低下，主要是为了使用的方便。
但这道题指明了时间和空间复杂度要求的，它作为一道中级题，肯定不是考我们python用的熟不熟练，所以我们要思考使用这些python方法的时候，有没有超过这些要求，要从算法层面来解决这道题。
所以我查找了一下python集合的内部实现，然而并没有百度到相关信息。不过，我在python高级编程这本书中找到了一些信息。里面讲解了字典和集合的具体实现细节，它使用了伪随机探测的散列表来作为字典的底层数据结构，而集合被实现为带有空值的字典。由于使用了散列表结构，所以它并不会通过遍历已有元素来确定是否重复了。
我们在做这道题时，也可以直接使用nums里的数值来作为存储的地址，比如直接创建一个长度为nums中最大值的数组t = [0]*max(nums)，然后用t(n)来存储元素的个数。这就是散列表的基本原理。但是这个最大值可能会大于nums的长度，这样就超出了O(1)的空间限制了。顺便说一下，排在第一的算法是错误的，因为他直接使用nums长度创建t数组，但这样可能导致数组越界。可能测试实例的数量比较少，没有测出来。
因此，我们是可以使用列表转集合或者使用字典来计数的方法的。由于字典获取元素的平均复杂度为O(1)，所以总的复杂度为O(n)。占用空间大小和nums的大小相同。
网友评论