Find the Duplicate Number: khi mảng là một linked list ẩn

Một mảng có n + 1 phần tử, mỗi giá trị nằm trong [1, n]. Theo pigeonhole principle, ít nhất một giá trị phải lặp lại. Tìm giá trị đó. Rồi đọc phần chú thích: không được sửa mảng, và bộ nhớ phụ phải là hằng số.

Ràng buộc thứ hai mới là toàn bộ câu đố. Không có nó, bạn sort in-place và quét trong O(n) — xong. Hoặc phủ định index đã thăm. Hoặc XOR. Tất cả những cách đó đều cần sửa mảng hoặc dùng O(n) bộ nhớ phụ. Gỡ bỏ chúng đi, những gì còn lại là hai cách tiếp cận thực sự thú vị: binary search trên miền giá trị, và cycle detection.

Đề bài

Cho mảng nums gồm n + 1 số nguyên, mỗi giá trị nằm trong [1, n], tìm số bị lặp lại duy nhất — mà không được sửa mảng và chỉ dùng bộ nhớ phụ hằng số. Đề gốc: LeetCode 287.

Ràng buộc:
- 1 <= n <= 10^5
- nums.length == n + 1
- 1 <= nums[i] <= n
- Tất cả số nguyên chỉ xuất hiện một lần, ngoại trừ đúng một số xuất hiện hai lần trở lên.

Constraints thực sự buộc bạn đi đâu

n lên đến 10^5. Điều đó loại bỏ ngay O(n^2) brute force — dù chỉ là vòng lặp đôi cũng là 10^10 phép tính trong trường hợp xấu nhất. Bạn cần tối đa O(n log n).

Mọi giá trị nằm trong [1, n] — một dải chặt chẽ, đã biết trước. Đó là đòn bẩy cho binary search trên giá trị, không phải index. Hầu hết bài toán binary search cung cấp cho bạn một mảng đã sắp xếp và yêu cầu tìm một target; ở đây bạn binary search trên không gian đáp án.

Mảng có độ dài n + 1 và tất cả giá trị trong [1, n]. Đây chính xác là cấu trúc mà Floyd's algorithm cần: nếu bạn coi mỗi index là một node và nums[i] là "con trỏ next," bạn có một functional graph trong đó mỗi node có đúng một cạnh ra. Giá trị trùng lặp là node mà hai cạnh khác nhau cùng trỏ vào — chính xác là điểm bắt đầu cycle.

Không được sửa mảng có nghĩa là kỹ thuật phủ định index bị loại. Bộ nhớ hằng số có nghĩa là hash set và sort vào cấu trúc phụ bị loại. Bạn chỉ có biến và phép tính con trỏ. Vậy thôi.

Approach 1: Hash set — đơn giản, nhưng vi phạm ràng buộc space

Đáng nêu rõ vì đây là thứ mọi người hợp lý đều viết đầu tiên.

class Solution:
    def findDuplicate(self, nums: list[int]) -> int:
        seen = set()
        for num in nums:
            if num in seen:
                return num
            seen.add(num)
        return -1  # không bao giờ xảy ra theo đảm bảo của đề

public class Solution {
    public int FindDuplicate(int[] nums) {
        var seen = new HashSet<int>();
        foreach (int num in nums) {
            if (seen.Contains(num)) return num;
            seen.Add(num);
        }
        return -1; // không bao giờ xảy ra
    }
}

Time: O(n). Space: O(n) — chính ràng buộc đang bị vi phạm. Hash set tăng tỉ lệ thuận với số giá trị phân biệt đã thấy, lên đến n phần tử.

Đây là giải pháp bạn viết trong code thực nếu không có ràng buộc follow-up. Nó đúng. Nó nhanh. Trong phỏng vấn, implement cái này trước rồi giải thích tại sao cần đi xa hơn là con đường hoàn toàn hợp lý.

Approach 2: Binary search trên miền giá trị — O(n log n), O(1) space

Insight then chốt là một lập luận đếm. Với bất kỳ giá trị m trong [1, n], đếm có bao nhiêu phần tử trong nums thỏa <= m. Gọi đó là f(m).

Nếu không có duplicate, các giá trị 1 đến m mỗi cái xuất hiện đúng một lần, nên f(m) = m. Duplicate làm lệch điều này: giá trị lặp đóng góp một lần đếm thừa ở đâu đó. Cụ thể, nếu duplicate là d, thì với mọi m >= d, f(m) ít nhất bằng m + 1 — có một giá trị "thừa" đóng góp vào các đếm từ d trở lên.

Tính đơn điệu này chính xác là những gì binary search cần. Bạn binary search trên m trong [1, n]:

• Nếu f(mid) > mid: duplicate nằm trong [left, mid], nên right = mid.
• Nếu f(mid) <= mid: duplicate nằm trong [mid+1, right], nên left = mid + 1.

Khi left == right, đó là duplicate.

class Solution:
    def findDuplicate(self, nums: list[int]) -> int:
        left, right = 1, len(nums) - 1  # miền giá trị [1, n]
 
        while left < right:
            mid = (left + right) // 2
 
            count = sum(1 for num in nums if num <= mid)
 
            if count > mid:
                right = mid
            else:
                left = mid + 1
 
        return left

public class Solution {
    public int FindDuplicate(int[] nums) {
        int left = 1, right = nums.Length - 1;
 
        while (left < right) {
            int mid = left + (right - left) / 2;
 
            int count = 0;
            foreach (int num in nums) {
                if (num <= mid) count++;
            }
 
            if (count > mid) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
 
        return left;
    }
}

Time: O(n log n) — log n bước binary search, mỗi bước cần một lần quét O(n). Space: O(1).

Trace qua nums = [1,3,4,2,2], n = 4

left=1, right=4

Lần 1: mid=2
  Đếm nums <= 2: [1,2,2] -> count=3
  3 > 2, nên right=2

Lần 2: left=1, right=2, mid=1
  Đếm nums <= 1: [1] -> count=1
  1 <= 1, nên left=2

left==right==2 -> return 2

Lập luận theo từng bước chậm: ở mid=2, ta tìm thấy ba giá trị tối đa là 2. Nhưng trong tập hoàn hảo {1,2}, sẽ chỉ có đúng hai. Đếm thừa có nghĩa là duplicate nằm đâu đó trong [1,2]. Ở mid=1, có đúng một giá trị tối đa là 1, đúng với {1}. Vậy duplicate không phải 1 — phải là 2.

Approach 3: Floyd's cycle detection — O(n), O(1) space

Đây là cách tiếp cận khiến bạn phải dừng lại và suy nghĩ. Nó biến mảng thành một implicit linked list, trong đó node i trỏ đến nums[i].

Với nums = [1,3,4,2,2]:

• Bắt đầu tại index 0 (luôn vậy). nums[0] = 1 nên 0 -> 1.
• nums[1] = 3 nên 1 -> 3.
• nums[3] = 2 nên 3 -> 2.
• nums[2] = 4 nên 2 -> 4.
• nums[4] = 2 nên 4 -> 2. Cycle.

Giá trị 2 xuất hiện hai lần (ở index 2 và 4). Hai cạnh trỏ vào node 2. Đó là nơi cycle bắt đầu. Điểm vào cycle chính xác là giá trị duplicate.

Floyd's algorithm tìm điểm vào đó trong hai phase.

Phase 1: di chuyển slow một bước và fast hai bước mỗi lần lặp. Chúng sẽ gặp nhau bên trong cycle.

Phase 2: reset một pointer về điểm bắt đầu (index 0). Tiến cả hai pointer một bước một lần. Chúng gặp nhau tại điểm vào cycle — giá trị duplicate.

class Solution:
    def findDuplicate(self, nums: list[int]) -> int:
        # Phase 1: tìm điểm gặp nhau trong cycle
        slow = nums[0]
        fast = nums[0]
 
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break
 
        # Phase 2: tìm điểm vào cycle
        slow = nums[0]
        while slow != fast:
            slow = nums[slow]
            fast = nums[fast]
 
        return slow

public class Solution {
    public int FindDuplicate(int[] nums) {
        // Phase 1: tìm điểm gặp nhau trong cycle
        int slow = nums[0];
        int fast = nums[0];
 
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
 
        // Phase 2: tìm điểm vào cycle
        slow = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
 
        return slow;
    }
}

Time: O(n). Space: O(1).

Trace tay qua nums = [1,3,4,2,2]

Phase 1 — cả hai bắt đầu tại nums[0] = 1:

Bước 1: slow=nums[1]=3, fast=nums[nums[1]]=nums[3]=2
Bước 2: slow=nums[3]=2, fast=nums[nums[2]]=nums[4]=2
slow==fast==2 -> gặp nhau tại 2

Phase 2 — reset slow về nums[0] = 1, fast giữ nguyên tại 2:

Bước 1: slow=nums[1]=3, fast=nums[2]=4
Bước 2: slow=nums[3]=2, fast=nums[4]=2
slow==fast==2 -> điểm vào cycle là 2

Trả về 2. Đúng.

Tại sao phase 2 hoạt động: lập luận khoảng cách

Gọi khoảng cách từ nums[0] đến điểm vào cycle là F. Gọi khoảng cách từ điểm vào cycle đến điểm gặp nhau (tiến về phía trước trong cycle) là a. Gọi phần còn lại của chu kỳ là b, nên độ dài cycle c = a + b.

Khi phase 1 kết thúc, slow đã đi F + a bước. Fast đã đi F + a + nc bước với n nguyên (nó đã vòng quanh cycle). Vì fast di chuyển nhanh gấp đôi: 2(F + a) = F + a + nc, nên F + a = nc, cho ra F = nc - a = (n-1)c + b.

Trong phase 2: một pointer bắt đầu từ đầu (0 bước), pointer kia ở điểm gặp nhau (a bước qua điểm vào cycle). Sau F bước nữa, pointer đầu ở điểm vào cycle. Pointer kia đã tiến F = (n-1)c + b bước từ điểm gặp nhau — quay (n-1) vòng đầy đủ rồi thêm b bước từ điểm gặp nhau — đưa nó đúng vào điểm vào cycle. Chúng gặp nhau tại điểm vào cycle. Đó là duplicate.

Các edge case đáng suy nghĩ

[1,1] (input nhỏ nhất có thể, n=1): cycle tầm thường — index 0 trỏ đến 1, index 1 trỏ đến 1, bạn ở lại 1 mãi. Floyd's phase 1 tìm điểm gặp ngay lập tức; phase 2 xác nhận 1 là điểm vào. Binary search trên [1,1] trả về 1 không cần lặp.

[3,3,3,3,3] (toàn cùng giá trị): mọi index ánh xạ đến 3, nên "linked list" là 0->3->3->3... với cycle tầm thường ngay tại 3. Floyd's hoạt động. Binary search tại mid=2: đếm giá trị <= 2 là 0, nên left=3. Tại mid=3: đếm là 5, lớn hơn 3, nên right=3. Trả về 3.

Duplicate xuất hiện nhiều hơn hai lần: đề bài nói "một hoặc nhiều" lần xuất hiện của cùng một giá trị. Floyd's không bị ảnh hưởng — cycle vẫn hình thành và điểm vào vẫn là duplicate. Binary search cũng không bị ảnh hưởng — lập luận đếm là f(m) > m bất cứ khi nào phần dư tích lũy từ các lần xuất hiện trùng lặp vượt qua midpoint.

Giá trị bằng n (biên trên): nếu duplicate là chính n, binary search cuối cùng hội tụ với left=right=n. Floyd's: một số index trỏ đến n, tạo cycle kết thúc tại n. Cả hai xử lý mà không cần special-case.

So sánh ba approach

Hash set là điểm khởi đầu hiển nhiên và là thứ bạn sẽ dùng trong thực tế nếu ràng buộc bộ nhớ hằng số không tồn tại. Binary search trên giá trị là điểm trung gian "thanh lịch nhưng chậm hơn" — nó thỏa ràng buộc và lập luận thì trong suốt. Floyd's tối ưu cả time lẫn space, nhưng chứng minh đòi hỏi một thực tế không hiển nhiên: điểm vào cycle bằng giá trị duplicate.

Cái nào tôi sẽ viết

Trong phỏng vấn khi cần chứng minh hiểu ràng buộc O(1): tôi bắt đầu với hash set, giải thích tại sao nó vi phạm ràng buộc, rồi trình bày Floyd's là giải pháp thực sự. Tôi viết binary search nếu người phỏng vấn yêu cầu bước trung gian hoặc nếu chứng minh Floyd's cảm thấy quá phức tạp dưới áp lực.

Trong code production với đúng bài toán này: cả ràng buộc O(1) lẫn không-sửa-mảng đều không tồn tại, nên tôi dùng hash set và tiếp tục. Floyd's đẹp nhưng nó đưa vào một chi phí nhận thức — kỹ sư tiếp theo đọc code sẽ mất năm phút để dựng lại chứng minh cycle-entry.

Lý do để biết Floyd's algorithm không phải bài toán cụ thể này. Đó là pattern: bất kỳ ánh xạ f: {0,...,n} -> {0,...,n} nào với codomain bị ràng buộc đều chứa một cycle, và Floyd's tìm điểm vào cycle trong O(n) time và O(1) space. Bạn sẽ thấy pattern đó lại trong Linked List Cycle II, trong một số cấu trúc hashing, và trong các cuộc tấn công mật mã vào state machine nhỏ.

Vị trí trong series linked-list và những gì đến tiếp theo

Bài này là bài đầu tiên trong series kết nối mảng với linked list bằng cách coi giá trị như pointer. Mọi thứ trước đó — đảo ngược, gộp, sắp xếp lại — nhận cấu trúc linked list tường minh. Ở đây bạn tự xây dựng cấu trúc ngầm và áp dụng cùng máy móc cycle detection.

Linked List Cycle II (142) là cha đẻ trực tiếp của thuật toán core trong bài này. Bài đó cho bạn một linked list tường minh và hỏi điểm vào cycle. Implementation Floyd's ở đây giống hệt; sự khác biệt chỉ là cách "node" và "con trỏ next" được biểu diễn (index mảng so với tham chiếu node thực).

Missing Number (268) là phần bù: thay vì tìm giá trị xuất hiện quá nhiều lần, tìm giá trị trong [0, n] không xuất hiện. Mẹo toán (tổng Gauss) xử lý trong O(n) time, O(1) space mà không cần cycle detection.

First Missing Positive (41) leo thang thách thức: tìm số nguyên dương nhỏ nhất còn thiếu trong mảng chưa sắp xếp, lại với O(n) time và O(1) space. Giải pháp mã hóa lại thông tin hiện diện vào mảng bằng cách lật dấu — chính xác là kỹ thuật sửa in-place mà bài 287 cấm tường minh.

Find All Numbers Disappeared in an Array (448) tổng quát hóa theo hướng khác: nhiều giá trị có thể bị thiếu. Nó dùng cùng framework index-as-pointer nhưng cho phép sửa mảng, đó là lý do tại sao nó có thể tìm tất cả giá trị thiếu trong một lần duyệt mà không cần Floyd's.

Pattern thống nhất 287, 142, và 41 là: khi giá trị nguyên phải sống trong một dải bị ràng buộc, dải đó có thể phục vụ như một không gian địa chỉ ngầm. Bạn có thể xây dựng cấu trúc dữ liệu từ chính mảng — hoặc như linked list (Floyd's) hoặc như presence bitmap (lật dấu). Ràng buộc cấm cách tiếp cận hiển nhiên (hashing, sorting) đang chỉ thẳng vào cấu trúc ngầm đó.