寻找重复数(python)

发表于 分类于 阅读次数： 本文字数： 1.1k 阅读时长 ≈ 1 分钟

题目是: 给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数

这也是leetcode上的第287道题.

寻找重复数

这里有前置条件, 数组中所有的元素都是在1到n之间! 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import pysnooper

#解法一
#这里有个比较有意思的地方在于, 完全利用了数组中所有元素都在1跟n之间.
#所以对数组求中位数,因为一定存在重复元素, 所以如果比中位数大的元素的个数大于中位数
#则说明重复元素存在在中位素的右边，反之在左边.
@pysnooper.snoop()
def findDuplicate(nums):
    low, high = 1, len(nums)-1

    while low < high:
        mid = (high + low) // 2
        count = sum(num <= mid for num in nums)
        if count <= mid:
            low = mid + 1
        else:
            high = mid
    return low

#解决二
#使用数组中的值作为索引下标进行遍历，遍历的结果肯定是一个环（有一个重复元素） 检测重复元素问题转换成检测环的入口 为了找到环的入口，可以进行如下步骤：
# 设置两个快慢指针， fast每次走两步，slow每次走一步，最终走了slow走了n步与fast相遇，fast走了2*n，fast可能比slow多饶了环的i圈，得到环的周长为n/i
# slow指针继续走, 且另设第三个指针每次走一步，两个指针必定在入口处相遇
# 假设环的入口和起点的距离时m
# 当第三个指针走了m步到环的入口时
# slow刚好走了n + m步，换句话说时饶了环i圈（环的周长为n/i）加m步（起点到入口的距离）
#得到相遇的是环的入口，入口元素即为重复元素

@pysnooper.snoop()
def findDuplicate2(nums):
    if len(nums) > 1:
        slow = nums[0]
        fast = nums[nums[0]]
        while slow != fast:
            slow = nums[slow]
            fast = nums[nums[fast]]
        #如果些是 快慢指针相遇, 则说明相遇的点为环内的点
        entry = 0
        while entry != slow:
            entry = nums[entry]
            slow = nums[slow]
        return entry
    return -1

参考文章: