287. Find the Duplicate Number

題意

在給定的一個包含 n + 1 個整數的數組中，這些整數都在 1 到 n 之間（包括 1 和 n）
- 其中至少有一個數字是重複的
- 目標是找到這個重複的數字
- 不能修改數組（例如排序數組），並且只能使用**O(1)** 空間複雜度

限制

1 <= n <= 10^5
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.

思考

暴力解法：這種方法會遍歷數組並使用一個額外的 **unordered_map**來記錄每個數字出現的次數
- 當發現某個數字的計數超過一次時，即可判定該數字為重複
- 但此法不符合題目對於空間複雜度的要求
數字映射標記法：
- 觀察到所有的數字都在 1 到 n 之間，可以將數組的索引作為數字本身的映射（即數字 i 映射到索引 i）
- 遍歷數組時，將遍歷到的數字對應索引的數組值變為其相反數
- 如果某次遍歷發現某個索引處的值已經是負的，則表示該索引代表的數字已經出現過一次，即為重複的數字
考慮到題目的要求，不能使用額外的數據結構來存儲每個數字的計數，也不能修改原始數組
- 此問題類似 Linked List Cycle
- 使用快慢指標，可以在滿足題目條件的情況下找到重複數
  - 因為存在重複的數字，數組可以被看作是一個隱式的 cyclic linked list
  - 初始化兩個指標，都從數組的起始位置開始
  - 慢指針每次移動一步，快指針每次移動兩步，其中重複的數字是循環的入口
  - 當快慢指針第一次相遇時，將快指針重置到起始位置，然後兩個指針都以相同的速度移動，當它們再次相遇時，相遇點即為重複數

Solution

需要修改 array 的解法

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        for (const int num : nums) {
            const int id = abs(num);
            if (nums[id] < 0) {
                return id;
            }
            nums[id] = -nums[id];
        }
        return -1;
    }
};

符合題意的寫法

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        if (nums.size() <= 1) {
            return -1;
        }

        int fast = 0;
        int slow = 0;
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);

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

287. Find the Duplicate Number​

題意​

限制​

思考​

Solution​

287. Find the Duplicate Number

題意

限制

思考

Solution