287. Find the Duplicate Number
Tags:
Medium
Skills:
Two pointerGraph
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Để giải bài toán "Find the Duplicate Number" trên LeetCode, bạn cần tìm một số bị lặp lại trong mảng chứa n+1 số nguyên trong khoảng từ 1 đến n
Approach - Floyd’s cycle detection
- Xem mỗi giá trị trong mảng như một điểm trong đồ thị, với giá trị tại mỗi chỉ số là liên kết đến chỉ số tiếp theo
- Sử dụng two pointer (slow and fast) để tìm chu kỳ trong đồ thị. Chu kỳ này sẽ chỉ ra số bị lặp lại
Solution - Floyd’s cycle detection
💡
Điểm giao nhau trong chu kỳ trong nhất thiết là điểm bắt đầu cảu chu kỳ
Sau vòng lặp do-white nếu 2 pointer gặp nhau điều này chứng minh
- Có một chu kỳ tồn tại trong mảng
- Hai con trỏ
slowvàfastđang ở một điểm trong chu kỳ, nhưng điểm này không nhất thiết là điểm bắt đầu của chu kỳ.
Để tìm chính xác điểm bắt đầu của chu kỳ, chúng ta cần thực hiện thêm bước thứ hai: đặt lại con trỏ fast về đầu mảng và di chuyển cả slow và fast từng bước một cho đến khi chúng gặp nhau. Điểm gặp nhau này chính là điểm bắt đầu của chu kỳ, và giá trị tại vị trí đó là số bị lặp.
typescripttypescript
1function findDuplicate(nums: number[]): number {
2 let slow = nums[0]
3 let fast = nums[0]
4
5 do {
6 slow = nums[slow]
7 fast = nums[nums[fast]]
8 } while (slow !== fast)
9
10 fast = nums[0];
11 while (slow !== fast) {
12 slow = nums[slow];
13 fast = nums[fast];
14 }
15
16 return slow
17};