超透彻解析leetcode有趣的题。287. Find the Duplicate Number

心已赠人 2023-07-18 06:50 60阅读 0赞

问题描述：

找到重复数字。有n+1个位置\[0,n\],却取值是整数从\[1，n\]取，比如\[1,2,3,4,5,1\]由于序号从0开始，所以一共0,1,2,3,4,5.一定有一个重复数值。找到这个重复数值。

Input: [1,3,4,2,2]
    Output: 2

此处默认python数组，特点是序号从零开始。其实感觉除了matlab都是从零开始的。

这个问题需要用o(1)的存储，以及o(n^2)时间，我对o(n)解法很感兴趣。这篇博客将用例子的形式解读最佳解法。

[原题][Link 1]，[解法][Link 2]

0 1 2 3 4 5
    1 2 3 5 1 4

上面数据实际上是个数组num，第一行是位置，第二行是对应的数值。所以num(0)=1,num(1)=2....

ind=0,如果按照ind=num(ind)进行解读会这样

ind=num(0)=1,下一次访问位置ind=1

第二次使用ind=num(ind)

ind=num(ind)=num(1)=2

如此重复，将ind取值按照顺序记录会有：0-1-2-3-5-4-1

注意，这里到了1之后，已经不用再去读取num了，因为下一个一定是2，毕竟你以前已经走到过1这个位置，并且读取了2不是吗，所以下一次再读取会有区别吗？不会的。

所以这就成了一个循环：0-1-2-3-5-4-1-2-3-5......

由于我本人向来多疑，所以：

*这个循环是一定发生的吗？为什么会发生呢？*

一定会发生的，因为num(0)=1,num(4)=1,所以不论这个序列有多长，只要0被访问，下一个一定是1，只要4被访问，下一个一定是1.序列中两次是1，上面已经解释过了，一定会重复1-2-3-5-4....

1，4一定会被访问，因为数列有六个位置，却只能写1-5，毕竟要有重复的数字，所以某个num(x)=4/1

*还有一个问题，会不会有循环提前比如2-3-2-3-2-3...这样先循环下去了？*

如果中间出现

2 3
    3 2

*那么num2=3 num3=2不就循环了吗？*但是，如果真的出现这样的数对，他们是不会被访问的，毕竟，**除了3谁会想起2呢？**

*如果2是重复数字比如例二：*

0 1 2 3 4 
    1 2 3 2 0

就不一样了，0-1-2-3-2-3-2....

*我先访问0重要吗？*

重要的，因为很有可能0的位置就存储的是重复数值，如果没有从零开始，那么这个位置的数值永远访问不到了因为数组数值取值范围没有0，比如上面的先从5开始则是5-4-1-2-3-5-4-1-2-3，这显然是错误的循环。**wow我举得例子好好。**

比如先从5开始

**所以目前毫无疑问，ind=num(ind)是一定会循环访问的，并且首尾都是那个罪魁祸首，循环数字。**

下面就是找到这个首尾，可惜的是存储空间必须是o(1)也就是常数个，可以是1，2，3，4却不可以是n，所以这个序列0-1-2-3-5-4-1是存不下来的，*那么怎么找到这个重复数字呢？*

也就是说有一个变量P一直可以以0-1-2-3-5-4-1-2..变化着，我们要找到变化过程中的圈圈，这个可以参考操场跑步，有人跑得快，有人跑得慢，如果跑得快的人很快，那么慢的人一定会被套圈。比如快的跑了两圈，慢的刚跑一圈。

操场两百米，b跑步速度是a两倍，什么时候套圈呢？就是起点的时候，a跑了200，b跑了400，两人都到了起始点。那么如果两个人一开始出发从一个小路开始的呢？注意循环P是0-1-2-3-5-4-1-2前面不是从1开始的。所以这里假设从小路开始，参考图片：meeting point是相遇点，黄色部分就是小路，也就是1之前的，比如本例就是0，1就是我们要的重复数值。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNDk4NTM_size_16_color_FFFFFF_t_70][]

** 这个图种画绿色部分其实应该和黄色部分一样长，多跑了一段，那么最后让两人都从起点回退一段路，这段路应该和小路一样长。也就是x=z**.我是拍脑袋想的，严谨的可以自己画个图，比如画出b跑了一圈a在哪之类的,也可以自己写公式，[最后能推导出x=z的][Link 2]。因为我们不是求多长，而是求跑道的起始点。小道部分绿色的就是0,起始点就是1，相遇点在哪还不知道。不过可以肯定，循环的起始点就是我们要的重复数值。可以通过找相遇点获得。

相遇点太容易了，这样出来的slow和fast都是相遇点（别忘了是数组的index）

int slow = nums[0];
    		int fast = nums[nums[0]];
    		while (slow != fast)
    		{
    			slow = nums[slow];
    			fast = nums[nums[fast]];
    		}

slow（a）:0-1-2-3-5-4-1-2-3-5

fast（b）:1-3-4-2-5........其中5就是相遇点我多写了一些slow，所以能够看明白点。实际上写道5就可以了。fast隔一个取一次。

然后的任务是找起始点。

fast = 0;
    		while (fast != slow)
    		{
    			fast = nums[fast];
    			slow = nums[slow];
    		}
    		return slow;

然后让fast重新开始跑，slow则继续跑，两者相遇的时候就是起点。

因为比较慢的a还有一段路没跑完，并且小路就等于没跑完的路程，那我再找个c，让他和a以同样的速度，从小路起点出发，a则还是继续从相遇点跑，最终会相遇于起始点也就是1.

反映到例子上就是，我们发现相遇点5了之后

slow（a）：4-1

slow（c）：0-1

好，相遇点找到了，1.

**完结撒花求点赞。**

还有一种同样时间复杂度以及空间复杂度的算法，因为有些[教程][Link 3]讲的已经很好的，这里只给代码：

class Solution:
        def findRepeatNumber(self, nums: List[int]) -> int:
            for i in range(len(nums)):
                while i != nums[i]:
                    t = nums[i]
                    if nums[i] == nums[nums[i]]:
                        return nums[i]  
                     
                    nums[i], nums[t] = nums[t], nums[i]

[Link 1]: https://leetcode.com/problems/find-the-duplicate-number/
[Link 2]: https://leetcode.com/problems/find-the-duplicate-number/discuss/72846/My-easy-understood-solution-with-O%28n%29-time-and-O%281%29-space-without-modifying-the-array.-With-clear-explanation.
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNDk4NTM_size_16_color_FFFFFF_t_70]: /images/20230528/d2e9d5a6012a4ece9ae3c261548d84f2.png
[Link 3]: https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/solution/shu-zu-zhong-de-zhong-fu-shu-zi-setji-he-yuan-di-j/