找到重复的数字（龟兔赛跑算法）

假设有一个数组，数组里有n+1个数，每个数范围是1-n，且只有一个重复数字，找到这个重复数字并返回如：[1,2,3,2,4]有5个数，每个数范围为1-4现在的任务是找到2这个数字普通方法1：可以先排序，遍历一次，然后对比两个元素是否相同#pythonnums.sort()for num in nums:if num==numreturn num//c++#inclu...

cornorghost

672人浏览 · 2020-02-29 15:33:19

cornorghost · 2020-02-29 15:33:19 发布

假设有一个数组，数组里有n+1个数，每个数范围是1-n，且只有一个重复数字，找到这个重复数字并返回如：

[1,2,3,2,4]有5个数，每个数范围为1-4

现在的任务是找到2这个数字

普通方法1：可以先排序，遍历一次，然后对比两个元素是否相同

#python
nums.sort()
for num in nums:
	if num==num
		return num

//c++
#include <algorithm>
sort(nums.begin(),nums.end())
for(int i=1;i<nums.size();i++)
{
	if(nums[i]==nums[i-1]):
		return nums[i];
}

这个方法很简单易懂，但是如果要求时间效率再高点呢

普通方法2：用哈希表（字典或者集合），牺牲内存减少排序的时间

#python
result={}
for num in nums
	if num  in result:
		return num
	result[nums[i]]=True

//c++
#include <map>
map<int,bool>result;
for(int i=1;i<nums.size();i++)
{
	if(result.find(nums[i])!=result.end())
	{
		return nums[i];
	}
	result[nums[i]]=true;
}

归兔赛跑法：定义两个指针，一个每次向前两步，一个每次向前一步，如果数组里有重复的数字，这两个指针一定会相遇，相遇后，快的指针重置到数组起点，两个指针在同时按步数为1的方法前进，再次相遇的数字即为重复数字

#python
tortoise=nums[0]
hare=nums[0]

while True:
	tortoise=nums[tortoise]
	hare=nums[nums[hare]]
	if tortoise==hare:
		break
ptr1=nums[0]
ptr2=tortoise

while True:
	ptr1=nums[ptr1]
	ptr2=nums[ptr2]
	if ptr1==ptr2:
		return ptr1