LeetCode [287] Find the Duplicate Number

 287. Find the Duplicate Number

Medium

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one duplicate number in nums, return this duplicate number.

Follow-ups:

1. How can we prove that at least one duplicate number must exist in nums? 
2. Can you solve the problem without modifying the array nums?
3. Can you solve the problem using only constant, O(1) extra space?
4. Can you solve the problem with runtime complexity less than O(n2)?

 

Example 1:

Input: nums = [1,3,4,2,2]
Output: 2

Example 2:

Input: nums = [3,1,3,4,2]
Output: 3

Example 3:

Input: nums = [1,1]
Output: 1

Example 4:

Input: nums = [1,1,2]
Output: 1

 

Constraints:

• 2 <= n <= 3 * 104
• nums.length == n + 1
• 1 <= nums[i] <= n
• All the integers in nums appear only once except for precisely one integer which appears two or more times.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

//C++: 32ms class Solution { public: int findDuplicate(vector<int>& nums) { sort(nums.begin(), nums.end()); for(int i=1; i<nums.size(); ++i){ if(nums[i]==nums[i-1]) return nums[i]; } return false; } }; //C++: 16ms class Solution { public: int findDuplicate(vector<int>& nums) { int n = nums.size(); bool cont = true; while(cont){ cont = false; for(int i=0; i<n; ++i){ if(nums[i]!=i+1 && nums[nums[i]-1]!=nums[i]){ swap(nums[i], nums[nums[i]-1]); cont = true; } } } for(int i=0; i<n; ++i){ if(nums[i]!=i+1) return nums[i]; } } }; //Java class Solution { public int findDuplicate(int[] nums) { int s = nums[0], f = nums[nums[0]]; while(s!=f){ s = nums[s]; f = nums[nums[f]]; } // System.out.println(s +" "+f); s = 0; while(s!=f){ s = nums[s]; f = nums[f]; } return f; } }