数组中重复的数

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

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

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

推荐文章:

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

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

每天微学习,

长按加入一起成长.

原文发布于微信公众号 - 谭小谭(tanstory)

原文发表时间:2019-04-02

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券