寻找重复元素可以化为寻找含环链表的环入口
我们常常会碰到一些找出重复元素的问题
普通而暴力的解法是:
- 1.两两比较法。所有元素间两两比较，相同时返回。时间复杂度O(n2)，空间复杂度O(1)
- 2.登记法。利用字典记录元素出现的次数，遍历一次所有元素，时间复杂度O(n)，空间复杂度O(n)
实际上，还可以换一个角度看待元素重复这个现象：
当我们再次访问到重复的元素时，感觉就像转了一圈又回到这个元素一样。从这个思维角度看，只要设计好访问元素的机制，对重复元素的访问就可以形成一个环，而重复的元素正是这个环的入口
列表[3,1,2,5,4,3]，重复元素是3。我们把3看成环的入口，那么在将要构造的含环链表中，这两个重复的3要对应同一个结点--环的入口结点。怎么让两个3对应同一个结点呢？我们这样设计结点：
node:
node.val = value
node.next = list[node.val] = list[value]
即
结点值=元素值value，
next指针 = list[元素值] =list[value]
可见，整个结点的属性（值和next指针）都由元素值唯一确定。这样一来，[3,1,2,5,4,3]中的首尾3对应的结点都是
node.val = 3
node.next = list[3] # 即元素“5”对应的结点
如此一来，当访问到list末尾的3时，相当于回到了头部的3对应的结点，就形成了一个环
列表转链表
事实上，基于【寻找重复元素化为寻找含环链表的环入口】这个想法，我们可以更一般化地讨论一下列表转为链表的内在规律
当列表中不重复的元素的【值恰好与它的下标相等】时，对应的结点为：
node.val = value
node.next = list[value] = self # 即next指向自己
由于这些结点自己指向自己，因此都是独立的，不与其他元素相连，自成一个单结点环，也就不会被访问。这等价于做了剪枝工作
如 我们对[3,1,2,5,4,3]的访问过程如下：
3 -- 5 --3 不断循环，而元素“1”“2”“4”由于value = index 且不重复，从而自成单结点环，不被访问列表中，不重复的元素也能成环--双结点环
如 [1,4,3,2,4,5]，按照上述的结点设计转化为链表，会形成：
- 含环链表1--4--4
- 双结点环3--2
- 单结点环5
综上，列表转链表时，无论是否含有重复元素，都可能出现解体现象，即一个列表产生多个链表或环
- 当列表无重复元素时，可以产生单结点环，双节点环，以及无环链表
-
当列表有重复元素时，可以产生单结点环，双节点环，以及含环链表
列表转链表.jpg
寻找重复元素例题
一个包含 n + 1 个整数的数组 nums，元素值都在[1, n]内，且存在一个重复出现的整数，找出这个重复的数。
示例
输入: [1,3,4,2,3]
输出: 3
将寻找列表重复元素转化为寻找含环链表的环入口：
# node:
# value: val
# next: nums[val]
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
slow = fast = 0
while fast is not None:
fast = nums[nums[fast]]
print("fast is %s" % str(fast))
slow = nums[slow]
print("slow is %s" % str(slow))
if fast == slow:
break
fast = 0
while fast != slow:
slow = nums[slow]
fast = nums[fast]
return slow
3 is returned and the info printed is below:
fast is 3
slow is 1
fast is 4
slow is 3
fast is 2
slow is 2
可见链表结点的访问依次是0--1--[3--2--4--3(环)]
问题思考：为什么要约定列表元素值在[1, n]？为什么取0不可以？
- 程序中，链表的头结点是额外创造的0结点，其next指针是list[0]，指向l第0个元素。如果列表元素能取0，那么在列表只有一个元素为0且所有元素不重复的情况下，如[1,2,3,4,5,0,6,8,9]，列表中的0和头结点0会形成环，将环入口结点0返回。这时程序的逻辑发生了改变，返回了错误的结果
网友评论