題目網址：https://leetcode.cn/problems/find-the-duplicate-number/

題意：給一有 n + 1 個數的 array nums, 每個元素值皆在 [1, n], 剛好只有一數字重複, 求重複的數字。

注意：只能使用 $O(1)$ space, 且不能改變 nums

進階：設計 $O(n)$ time 的演算法

Solution 1：

想法：利用 Binary Search, 先在 [1, n] 中找中點 mid, 然後判斷整個 nums 中 ≤ mid 的元素個數 cnt。若 cnt > mid 代表有重複, 則往左繼續找

不要考慮 nums, 只需要考慮數字都在 1 到 n 之間
nums = [1,3,4,2,2] 此時數字在 1 到 4 之間

mid = (1 + 4) / 2 = 2, nums 中 ≤ 2 的有3個(1,2,2), 1到2中肯定有重複, 往左搜尋 ➔ right = 2
mid = (1 + 2) / 2 = 1, nums 中 ≤ 1 的有1個(1), 2到2中肯定有重複, 往右搜尋
➔ left = 2, left < right 不成立
➔ 所以重複的數是 2
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int left = 1, right = nums.size() - 1;

        while (left <= right) {
            const int mid = left + (right - left) / 2;
            int count = 0;

            for (const auto& num : nums) {
                if (num <= mid) {
                    ++count;
                }
            }

            if (count > mid) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};
  • time：$O(n \cdot log(n))$
    • $O(log(n))$：Binary Search, while loop 得做 $O(log(n))$ 次
    • $O(n)$：while loop 每迭代一次, for loop 都得遍歷 nums
  • space：$O(1)$ ➔ 只需常數空間

Solution 2：

想法：將此問題轉換成 linked list cyle, 利用 slow & fast pointers 找出 cycle 的起點, 可參考 142. Linked List Cycle II

nums = [1,3,4,2,2]

第一個 0 代表從 idx = 0 開始
下一個移動到 nums[0] = 1
下一個移動到 nums[1] = 3, 依此類推
因為有重複數, 代表會有兩個數指向同一個數 e.g. nums[3] 和 nums[4] 都指向 nums[2] = 4
0->1->3->2->4->2, cycle: 2->4->2

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = 0, fast = 0;

        // 找出 slow 和 fast 相遇的點
        while (true) {
            slow = nums[slow];
            fast = nums[nums[fast]];
            if (slow == fast) {
                break;
            }
        }

        // 找出 cycle 的起點
        slow = 0;
        while (fast != slow) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
};
  • time：$O(n)$ ➔ 遍歷 linked list
  • space：$O(1)$ ➔ 只需常數空間