首页 > 代码库 > 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
一、二分法查找,如果有个数重复,那么这个数肯定在前半部分或者后半部分,当在前半部分时,数组中小于等于中间数(这里的中间数指的是1-n中间的那个数)的个数应该大于中间数,通过遍历数组查找小于等于中间数的个数,再和中间数比较,如果中间数大,说明在前半部分,这时要改变mid的值。中间数mid的值得求法:mid = min + (max - min)/2,要改变mid可以通过改变max和mid,在前半部分时就max=mid,在后半部分就min = mid+1,最后当min = max时就找到了重复的数了。
public class Solution { public int findDuplicate(int[] nums) { int l = nums.length; int mid = 0; int min = 1; int max = l-1; while(min < max) { int count = 0; mid = min + (max - min)/2; for(int i = 0;i<l;i++) { if(nums[i] <= mid) count ++; } if(count > mid) { max = mid; } else min = mid +1; } return min; } }
二、找环路起点法
假设数组中没有重复,那我们可以做到这么一点,就是将数组的下标和1到n每一个数一对一的映射起来。比如数组是213
,则映射关系为0->2, 1->1, 2->3
。假设这个一对一映射关系是一个函数f(n),其中n是下标,f(n)是映射到的数。如果我们从下标为0出发,根据这个函数计算出一个值,以这个值为新的下标,再用这个函数计算,以此类推,直到下标超界。实际上可以产生一个类似链表一样的序列。比如在这个例子中有两个下标的序列,0->2->3
。
但如果有重复的话,这中间就会产生多对一的映射,比如数组2131
,则映射关系为0->2, {1,3}->1, 2->3
。这样,我们推演的序列就一定会有环路了,这里下标的序列是0->2->3->1->1->1->1->...
,而环的起点就是重复的数。
所以该题实际上就是找环路起点的题,和Linked List Cycle II一样。我们先用快慢两个下标都从0开始,快下标每轮映射两次,慢下标每轮映射一次,直到两个下标再次相同。这时候保持慢下标位置不变,再用一个新的下标从0开始,这两个下标都继续每轮映射一次,当这两个下标相遇时,就是环的起点,也就是重复的数。
下边是找环路起点的经典做法,要记住
int slow = nums[0]; int 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