首页 > 代码库 > 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.
Reference
public int FindDuplicate(int[] nums) { int slow = 0; int fast = 0; while(true) { slow = nums[slow]; fast = nums[nums[fast]]; if (slow == fast) break; } int t=0; while(true) { slow = nums[slow]; t = nums[t]; if (slow == t) break; } return slow; }
public int FindDuplicate(int[] nums) { int left = 1; int n = nums.Count()-1; int right = nums.Count()-1; while(left< right) { int mid = left + (right - left)/2; int sumLeft = 0; for(int i = 0 ;i< nums.Count();i++) { if(nums[i]<=mid) sumLeft++; } if(sumLeft <= mid) left = mid+1; else right = mid; } return left; }
287. Find the Duplicate Number
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。