[leetcode 287] Find the Duplicate Number

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.

 

[1, n]이 모두 존재하는 배열에서 하나가 중복될 때 중복되는 숫자를 찾아라. 

 

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.

문제 풀이:
- 첫 번째 풀이: follow up 질문을 무시하고 단순하게 풀었다.

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int answer;
        for(int i=0; i<nums.size()-1; i++){
            if(nums[i] == nums[i+1]){
               answer = nums[i];
            }
        }
        return answer;
    }
};

 

- follow up 질문을 모두 지켜서 풀기: cycle detection 알고리즘 사용

- floyd's tortoise and hare 

eazymean.tistory.com/101

[알고리즘] Floyd's tortoise and hare

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        
        int tortoise = nums[0];
        int hare = nums[0];
        
        do {
            tortoise = nums[tortoise];
            hare = nums[nums[hare]];
        }while(tortoise != hare);
        
        tortoise = nums[0];
        
        while(tortoise != hare){
            tortoise = nums[tortoise];
            hare = nums[hare];
        }
        
        return hare;
    }
};