数组中重复的数



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


有一个长度为 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)) 

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


关键词: 算法

网友留言(0条)

发表评论