287. Find the Duplicate Number - Medium

前往題目

想法

• 毫無想法，因為不能動array，然後一定要constant time

思路

這題連neetcode大大都說討厭，這是我第一次聽到他說不喜歡題目🤣總之就是一個沒看過的人根本就幾乎不可能30分鐘內想出來的問題

1. Linked List cycle
2. 快慢指針
3. Floyd's algo.

Code

這題背就對了

詳細解釋可以看Neetcode大大的影片或是討論區

class Solution {
    public int findDuplicate(int[] nums) {
        // Floyd's algo.

        // Init. pointers at the beginning
        int slow = 0, fast = 0;

        while (true) {
            slow = nums[slow];
            fast = nums[nums[fast]];
            if (slow == fast) break;
        }

        int slow2 = 0;

        // Move 1 step until meet
        // by mathematics
        while(true) {
            slow = nums[slow];
            slow2 = nums[slow2];
            if (slow == slow2) break;
        }

        return slow;
    }
}

2024/04/23

• 背誦題😂

2025/04/25

• 這個解法似乎更好理解，直接把原始的 array 拿來當記錄，不管那個位置上的數字，只在意 index
• 反正有重複的話就一定會再回到同一個 index

public class Solution {
    public int findDuplicate(int[] nums) {
        for (int num : nums) {
            int idx = Math.abs(num) - 1;
            if (nums[idx] < 0) {
                return Math.abs(num);
            }
            nums[idx] *= -1;
        }
        return -1;
    }
}