Z.S.K.'s Records

寻找重复数(python)

题目是: 给定一个包含 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

参考文章:

转载请注明原作者: 周淑科(https://izsk.me)


 wechat
Scan Me To Read on Phone
I know you won't do this,but what if you did?