黄页网站 php,培训机构招生7个方法,网站开发项目报价单,做网站免费搭建一、题目
给定一个长度为 n1 的数组nums#xff0c;数组中所有的数均在 1∼n1 的范围内#xff0c;其中 n≥1。
请找出数组中任意一个重复的数。
样例
给定 nums [2, 3, 5, 4, 3, 2, 6, 7]。返回 2 或 3。
二、解析
解决这个问题的一种有效方法是使用快慢指针#xf…一、题目
给定一个长度为 n1 的数组nums数组中所有的数均在 1∼n1 的范围内其中 n≥1。
请找出数组中任意一个重复的数。
样例
给定 nums [2, 3, 5, 4, 3, 2, 6, 7]。返回 2 或 3。
二、解析
解决这个问题的一种有效方法是使用快慢指针也称为龟兔赛跑算法Floyds Cycle Detection Algorithm。该算法的基本思想是在一个循环链表中快指针和慢指针分别以不同的速度移动如果存在环则两者最终会相遇。
在这个问题中可以将数组视为一个链表数组中的元素值作为下一个节点的索引构成一个链表。因为题目保证了数组中的元素值在 1 到 n 的范围内所以数组中不存在负数也不存在索引超出数组范围的情况。
原理
当我们把数组中的元素看作链表中的节点时题目要求找到数组中的任意一个重复数实际上就是在链表中找到环的入口点。快慢指针算法的核心思想是利用两个不同速度的指针如果存在环这两个指针最终会相遇。
下面是算法的基本思路 初始化使用两个指针一个慢指针 slow 和一个快指针 fast初始时都指向数组的第一个元素 nums[0]。 寻找相遇点快指针每次前进两步慢指针每次前进一步直到两者相遇。相遇时说明链表中存在环。 重置一个指针将其中一个指针例如慢指针重置到数组的第一个元素 nums[0]而另一个指针保持在相遇点。 寻找环的入口点两个指针再以相同速度前进直到它们再次相遇。相遇点即为环的入口点也即重复的数。
这个原理的关键在于当两个指针相遇时说明链表中存在环。在寻找环的入口点时将一个指针重置到链表头然后两个指针以相同的速度前进它们再次相遇的点就是环的入口点。在这个问题中环的入口点对应于数组中的重复数。
这个算法的时间复杂度为 O(n)其中 n 是数组的长度。算法的空间复杂度为 O(1)因为只使用了常数额外的空间。
下面是用C语言实现的代码
#include stdio.hint findDuplicate(int* nums, int numsSize) {// 初始化快慢指针int slow nums[0];int fast nums[0];// 寻找相遇点do {slow nums[slow];fast nums[nums[fast]];} while (slow ! fast);// 重置其中一个指针并寻找环的入口点——这里可以想一想为什么Aslow nums[0];while (slow ! fast) {slow nums[slow];fast nums[fast];}// 返回环的入口点即重复的数return slow;
}int main() {// 示例用法int nums[] {1, 3, 4, 2, 2};int numsSize sizeof(nums) / sizeof(nums[0]);int duplicate findDuplicate(nums, numsSize);printf(Duplicate: %d\n, duplicate);return 0;
}A让我们来解释一下为什么这个过程能找到环的入口点 首次相遇点当快指针和慢指针首次相遇时它们分别走过的步数之间存在关系快指针走过的步数是慢指针的两倍。假设两者相遇时慢指针走了 k 步则快指针走了 2k 步其中 k 是环的长度的整数倍。 重置指针位置将慢指针重置到数组的第一个元素 nums[0]保持快指针在相遇点不动。 再次相遇此时慢指针从数组头部开始而快指针还停留在相遇点。它们以相同的速度前进当慢指针再次走了 k 步时快指针走了 2k 步即正好走完了环的若干圈同时再次相遇。 相遇点即为入口点再次相遇的点就是环的入口点。这是因为在第一次相遇后慢指针已经在环内走了若干圈而重置后再次相遇时慢指针还需走若干圈才能达到入口点而快指针已经在环内等待因此它们在入口点相遇。
这个过程的本质是根据快慢指针相遇时快指针已经走过的步数是慢指针的两倍的特性找到环的入口点。这个算法的关键在于数学上的推理而实际上这种方法是基于龟兔赛跑算法的原理。
