Python剑指offer：数组中重复的数字

题目一：找出数组中重复的数字

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

思路一

解决这个问题一个简单方法是把输入的数组排序，将数组排序之后从排序的数组中找出重复的数字是一个很容易的事情，只需从头到尾扫描排序后的数组就可以了，排序一个长度为n的数组需要O(nlogn)时间。

思路二

还可以用哈希表来解决这个问题，从头到尾扫描数组中的每个数字，每扫描到一个数字的时候，就可以用O(1)的时间来判断哈希表里是否包含这个数字。如果哈希表里还没有这个数字，就可以把它加入哈希表里。如果哈希表包含这个数字，那么就找到一个重复数字。这个算法的时间复杂度是O(n)，但它提高效率是以一个大小为O(n)的哈希表为代价的。有没有可能有更好的算法，把空间复杂度降低到O(1)，答案是有的。

思路三

要想找到特定问题最优算法，一定要观察该特定问题的特点。而这个问题的特点是，数组中出现的数字都在0~n-1范围之内。那么根据这个特点，如果数组中没有重复数字，那么应该下标和数字是一一对应的关系。当数组中出现重复数字之后，我们可以想象一下，会出现多个数字对应一个下标，而有的下标不对应任何数字。

我们抓住这个特点，使用第二个哈希表的思路，不过我们可以不用重新建立新的哈希表。只需要在原有的数组上改就可以了。简单来说，我们就是捋顺改列表中元素和位置对应关系，让尽可能元素和位置是一一对应的。具体来说，从头到尾扫描数组中每个数字。当扫描到下标为i的数字时候，首先比较这个数字（比如说这个数字的值是m）是不是为等于i。如果是，接着扫描下一个数字。如果该位置的数值m不等于i。那么，就把这个数字m和第m个位置的数字进行比较，如果相等，就找到一个重复数字。如果他和第m个位置的数字不想等，就把第i个位置和第m个位置的两个位置的数字进行交换。把数字m放到他应有的位置上。

def repeatable_num(a):if a == []:return "请输入含有具体数值的数组"repeat_num = []for i in range(len(a)):if i != a[i]:if a[i] == a[a[i]]:repeat_num.append(a[i])else:temp = a[i]a[i] = a[temp]a[temp] = tempreturn repeat_num

总结

以上是生活随笔为你收集整理的Python剑指offer：数组中重复的数字的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。