上海 网站开发 兼职,网站手机客户端制作,oa办公系统开发,c 博客网站开发教程这道题真的是中等题吗#xff1f;我请问呢#xff1f;#xff1f;我怎么觉得是困难题呢#xff1f; 这道题的思路太难想了#xff0c;想不出来#xff0c;直接去看的这位大佬的题解#xff0c;写得很清楚。 这道题可以将其转化为环形链表问题#xff0c;可是为什么只要… 这道题真的是中等题吗我请问呢我怎么觉得是困难题呢 这道题的思路太难想了想不出来直接去看的这位大佬的题解写得很清楚。 这道题可以将其转化为环形链表问题可是为什么只要存在重复元素按照i - nums[i]的映射方式一定能构成环呢以下是我的思考
题目保证只存在一个重复的数其余数最多只出现一次由于下标范围为[0, n]有n 1个不同的下标但是数组中最多只会有n个一个数重复2次其余元素各不相同只出现一次也可能少于n个因此对于i - nums[i]的映射nums[i]的个数一定会小于i的个数所以一定会出现哈希冲突出现哈希冲突的就是我们要找的重复的数。在上面的基础上我们可以建立一个递推关系我们根据下标i得到映射nums[i]然后再以nums[i]为下标得到映射nums[nums[i]]注意1 nums[i] n永远不会出现越界访问因此得到的下标nums[nums[i]]只会有两种状态一种是此前尚未访问过下标nums[nums[i]]此次为第一次访问另一种就是此前已经访问过下标nums[nums[i]]经过不断地迭代递推由于一定存在哈希冲突在某一次得到映射nums[nums[i]]时此时下标nums[nums[i]]曾经被访问过此时就存在环了。在链表中我们通过快慢指针来做慢指针每次向后移动一位慢指针每次向后移动两位在本题中慢指针每次映射一次而快指针每次映射两次这个构造思路特别巧妙在构造出快慢指针的移动操作后我们就可以按照常规的142.环形链表Ⅱ来做了具体的思路可以看下我这篇博客。 下面是代码
class Solution {
public:int findDuplicate(vectorint nums) {int slow 0; //慢指针int fast 0; //快指针slow nums[slow];fast nums[nums[fast]];//一定存在环先让慢指针停留在特定位置while(slow ! fast){slow nums[slow];fast nums[nums[fast]];}//再定义一个慢指针int slow1 0;while(slow1 ! slow){slow1 nums[slow1];slow nums[slow];}return slow;}
};这道题是力扣hot100的最后一道刷完这道题还给了个勋章唉终于坚持下来了。
