287. Find the Duplicate Number

class Solution {
    public int findDuplicate(int[] nums) {
        Set<Integer> dup = new HashSet<Integer>();
        
        for (int n : nums) {
            if (dup.contains(n)) {
                return n;
            } else {
                dup.add(n);
            }
        }
        
        return -1;
    }
}

Runtime: 2 ms, faster than 49.24% of Java online submissions for Find the Duplicate Number.
Memory Usage: 40.2 MB, less than 16.10% of Java online submissions for Find the Duplicate Number.

처음에는 내사랑 쉬맵이를 이용~

Sol. 2

class Solution {
    public int findDuplicate(int[] nums) {
        int front = 0;
        int back = 0;
        
        while (nums[front] != nums[back]) {
            front = front + 1;
            back = back + 2;
            
            if (front > nums.length - 1) {
                front = front - nums.length;
            }
            if (back > nums.length - 1) {
                back = back - nums.length;
            }
        }
        
        return nums[back];
    }
}

우리의 trauma... Floyd's Circle Finding Algorithm을 사용했으니 큰 소득 x

class Solution {
  public int findDuplicate(int[] nums) {
    // Find the intersection point of the two runners.
    int tortoise = nums[0];
    int hare = nums[0];
    do {
      tortoise = nums[tortoise];
      hare = nums[nums[hare]];
    } while (tortoise != hare);

    // Find the "entrance" to the cycle.
    tortoise = nums[0];
    while (tortoise != hare) {
      tortoise = nums[tortoise];
      hare = nums[hare];
    }

    return hare;
  }
}

답지를 보니 내가 생각한 방법이 있긴 하고 빠르기도 한데... 왜 이렇게 되는지 모르겠음

Runtime: 0 ms, faster than 100.00% of Java online submissions for Find the Duplicate Number.
Memory Usage: 39.1 MB, less than 54.45% of Java online submissions for Find the Duplicate Number.

int findDuplicate3(vector<int>& nums)
{
	if (nums.size() > 1)
	{
		int slow = nums[0];
		int fast = nums[nums[0]];
		while (slow != fast)
		{
			slow = nums[slow];
			fast = nums[nums[fast]];
		}

		fast = 0;
		while (fast != slow)
		{
			fast = nums[fast];
			slow = nums[slow];
		}
		return slow;
	}
	return -1;
}