数组中重复的数

之前有写过 找出数组中只出现一次的数，今天再来看下怎么找出数组中重复出现的数。

有一个长度为 n 的数组，所有的数字都在 0~n-1 的范围，现在要求找出数组中任意一个重复的数字。

这个题目看起来很简单，看看下面几种思路。

思路一：

先给数组排序，然后再遍历一遍有序数组，依次比较相邻元素，就很容易能找出数组中重复的值。使用快排排序的话时间复杂度为 O(nlogn) 。

思路二：

利用空间换时间的思想，新建一个哈希表，然后遍历数组，每扫描一个元素都去哈希表里查找是否也存在该元素，如果存在，即找到一个重复的数，如果不存在，则将该元素保存到哈希表。这个思路的时间复杂度为 O(n)，但空间复杂度也为 O(n)。

思路三：

认真审题，你会发现有一些特点，长度为 n 的数组，且元素的大小范围为 0~n-1，如果没有重复的数字的话，那么数组排序后数字 i 就是下标 i 所在的位置了，即 arr[i] == i。所以我们可以巧妙利用数组的下标特性来寻找解决方案。

如果上面那句话还没看明白，看下面这个例子你就知道了。

#arr数组中没有重复元素的情况
#数组长度为7，元素范围为0-6
arr = [0,1,2,3,4,5,6]
arr[0] == 0
arr[1] == 1
arr[2] == 2

我们通过一个具体的例子来捋一捋思路，先准备一个数组。

arr = [4,1,1,3,5,2,5]

从头开始遍历数组，判断 arr[i] 是否等于 i，如果等于则无需任何操作继续往后遍历。

如果 arr[i] 不等于 i，则继续拿 arr[i] 和 arr[arr[i]] 比较，如果 arr[i] 和 arr[arr[i]] 相等，则找到一个重复的数，因为该数字在 i 下标和 arr[i] 下标同时出现了。

如果 arr[i] 和 arr[arr[i]] 不相等，那就交换他们的位置，交换的目的就是为了把 arr[i] 放到属于他的位置，保证 arr[i] == i。

交换了之后，再重复上面的比较、交换操作，直到找到一个重复的数。

arr = [4,1,1,3,2,5,5]

arr[0] != 0
则比较 arr[0] 和 arr[4]

arr[0] != arr[4]
则交换 arr[0] 和 arr[4] 的位置

新数组变成
arr = [2,1,1,3,4,5,5]

再从头开始遍历比较
arr[0] != 0
则比较 arr[0] 和 arr[2]

arr[0] != arr[2]
则交换 arr[0] 和 arr[2] 的位置

新数组变成
arr = [1,1,2,3,4,5,5]

再从头开始遍历比较
arr[0] != 0
则比较 arr[0] 和 arr[1]

arr[0] == arr[1]
找到一个重复的数

你可能会问，为什么要交换，交换的目的就是为了把元素放到属于它的位置上，要让这个数组满足 arr[i] == i，换句话说就是不断的调整数组，使其满足 arr[i] == i，比如数组中第一个元素 arr[0] 为 4 ，那就要把元素 4 放到下标为 4 的位置上去。下面是一份用 python 实现的完整代码，大家可以参考下。

# encoding=utf-8

def findDuplicate(arr):
    if arr is None:
        return False

    for i in arr:
        while arr[i] != i:
            if (arr[i] == arr[arr[i]]):#找到重复的值
                return arr[arr[i]]
            else:#如果不相等就交换位置
                temp = arr[arr[i]]
                arr[arr[i]] = arr[i]
                arr[i] = temp
    return False


arr = [4,1,1,3,5,2,5]

print(findDuplicate(arr))

看完这篇文章，大家主要是知道在处理有关数组这种数据结构的问题时，要善于利用数组下标这个隐藏的条件，如果文章对你有帮助，就点个在看哈，感谢支持。

推荐文章：

找出数组中只出现一次的数

我给自己配置的第一份保险

每天微学习,

长按加入一起成长.