首页 > 代码库 > 287. Find the Duplicate Number
287. Find the Duplicate Number
Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.
Note:
- You must not modify the array (assume the array is read only).
- You must use only constant, O(1) extra space.
- Your runtime complexity should be less than
O(n2)
. - There is only one duplicate number in the array, but it could be repeated more than once.
解题思路:首先去这个博客瞻仰一下http://keithschwarz.com/interesting/code/?dir=find-duplicate
这题目的思路巧妙在把数组数值转化成了索引,也就是把顺序数组变成了链表来用。构造出链表图之后,就使得该题变成了带环链表找进入链表的入口值。至于构造出的图为什么一定有环,这是因为n个值,n+1个索引,由鸽笼原理可知,总有一个数被指了两次,也就是重复出现的值,也就是环的entry。
class Solution { public: int findDuplicate(vector<int>& nums) { if(nums.size()<=1)return -1; int slow=nums[0],fast=nums[nums[0]]; while(slow!=fast){ slow=nums[slow]; fast=nums[nums[fast]]; } fast=0; while(slow!=fast){ slow=nums[slow]; fast=nums[fast]; } return slow; } };
287. Find the Duplicate Number
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。