《剑指offer》3.数组中重复的数字

唔，实习公司提转正时主动辞职了。然后一毕业就失业了，投了几十分简历，连个面试机会都不给。
于是决定闭门修炼，先把基础提上去吧。遂准备把剑指offer上面的题全部实现一遍。
剑指offer上的代码是用c++实现的，我主要是用的python，正好可以整一套python的版本。虽然网上也早有前辈用python实现过了。。。
但算法必须要自己理解了才是自己的，所以自己还是要全部实现一遍。
废话说完了，下面正式开始了。

题目一： 找出数组中重复的数字。
在一个长度为n的数组里所有数字都在0~n-1的范围内。
数组中某些数字是重复的，但不知道几个数字重复了，也不知道每个数字重复了几次。
请找出数组中任意一个重复的数字。
例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出重复的数字是2或者3。

使用python最简单的方法使用collections里的Counter方法。它会自动统计每一个元素出现的次数。最后输出所有个数大于1 的即可。内部实现是用的字典（哈希表），也可以直接用字典来做,相当于手动实现一遍Counter函数。

def duplicate_number(nums):
    c = collections.Counter(nums)
    return [x for x in c if c[x] > 1]

时间复杂度为O(n)，空间复杂度也为O(n)，因为需要维护一个n大小的哈希表。
书中提到了另一种算法。因为数组中所有数字的大小均在0~n-1的范围内。这个范围和数组的下标范围是一致的，意味着可以用数字直接做下标且不会越界。所以可以直接把数字调整到和数字相等下标的位置上。
比如题中给出的数组{2,3,1,0,2,5,3}，第一个数字是2，比较下标2上的数字1，发现不相等，那么把它和下标2上的数字对换，变成{1,3,2,0,2,5,3}。现在第一个数字是1，和下标1上的数字3还是不相等，那么再和下标1上的数字对换，变成{3,1,2,0,2,5,3}。这样一直换下去，确保每个数字都和它的下标是相等的。那么如果遇到重复的数字，比如下标4上的2，当它想换到下标2上时，发现下标2上已经有一个数字2了，那么就表示这个数字重复了。这样在本地数组上就完成了操作，不需要额外分配空间，所以空间复杂度就是O(1)。
python实现的代码如下：

def duplicate_number_method_2(nums):
    res = set()
    i = 0
    while i < len(nums):
        if nums[i] != i:  # 判断需不需要换位置
            c = nums[i]
            if nums[i] != nums[c]:  # 判断是不是重复的数字，不是则交换，是则添加到结果集中
                nums[c], nums[i] = nums[i], nums[c]
            else:
                res.add(c)
                i += 1
        else:  # 不需要换位置则直接跳到下一个
            i += 1
    return res

一个循环，虽然有时候i的值不会增加，但对于每个位置来说，要不交换，要么不交换，所以时间复杂度还是O(n)级别的。