Find the Duplicate Number
Bạn nhận được một mảng nums gồm n+1 số nguyên, mỗi số nằm trong khoảng từ 1 đến n. Chính xác một giá trị xuất hiện nhiều hơn một lần, có thể xuất hiện nhiều lần, và bạn trả về giá trị đó.
Giải bài toán mà không thay đổi nums và chỉ dùng một lượng bộ nhớ bổ sung hằng số.
Hàm
- numsinteger-array
- n+1 số nguyên, mỗi số nằm trong khoảng từ 1 đến n
- Trả vềinteger
- giá trị xuất hiện nhiều hơn một lần
Ràng buộc
1 ≤ n ≤ 104nums.length == n+11 ≤ nums[i] ≤ n- Chỉ có đúng một giá trị xuất hiện từ hai lần trở lên; mọi giá trị khác chỉ xuất hiện nhiều nhất một lần.
Ví dụ
- Đầu vào
- nums = [2, 5, 1, 3, 5, 4]
- Đầu ra
- 5
- Giải thích
- Ở đây,
nbằng 5, và số 5 nằm ở vị trí 1 và 4, nên đáp án là 5. Mọi giá trị khác từ 1 đến 5 đều xuất hiện một lần.
- Đầu vào
- nums = [4, 2, 4, 1, 4]
- Đầu ra
- 4
- Giải thích
- 4 xuất hiện ba lần, ở các vị trí 0, 2 và 4, còn 3 thì không xuất hiện lần nào. Một giá trị lặp lại có thể thay thế cho nhiều giá trị bị thiếu, nên đáp án là 4.
Câu hỏi mở rộng
Tìm kiếm nhị phân trên các giá trị vẫn giữ cả hai quy tắc trong thời gian O(n log n). Bạn có thể giữ chúng trong thời gian O(n) không?
Gợi ý
Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.
Mọi giá trị đều nằm trong khoảng từ 1 đến
n, và mảng có các vị trí từ 0 đếnn. Vì vậy, mọi giá trị cũng là một vị trí hợp lệ. Bắt đầu ở vị trí 0, nhảy đến vị trínums[0], rồi đến vị trí được giá trị đó chỉ định, và cứ tiếp tục như vậy. Điều gì phải xảy ra với đường đi đó?Quá trình di chuyển không bao giờ dừng lại và chỉ có
n+1vị trí để đi qua, nên nó rơi vào một vòng lặp. Vị trí mà quá trình đi vào vòng lặp được đi tới từ hai vị trí khác nhau, và cả hai vị trí đó đều có giá trị là vị trí ấy.Tìm lối vào vòng lặp bằng hai con trỏ bắt đầu từ vị trí 0: một con trỏ nhảy một bước mỗi lượt, con còn lại nhảy hai bước, cho đến khi chúng dừng ở cùng một vị trí. Sau đó, đưa một con trỏ về vị trí 0 rồi di chuyển cả hai, mỗi lần một bước. Chúng sẽ gặp nhau tại lối vào, đó là đáp án.
Lời giải
Tập hợp băm cần bộ nhớ cho từng giá trị, còn việc sắp xếp làm thay đổi nums. Mọi giá trị đều nằm trong khoảng từ 1 đến n, nên mỗi giá trị cũng là một vị trí hợp lệ: hãy xem nó như một liên kết. Lần đi từ vị trí 0 sẽ kết thúc ở một vòng lặp có điểm bắt đầu là giá trị trùng lặp, và hai con trỏ của Floyd tìm thấy nó trong O(n).
So sánh từng cặp
Đúng, nhưng không chạy xong với các test lớn nhất
Ý tưởng
So sánh từng vị trí với mọi vị trí phía sau nó, rồi trả về giá trị của cặp đầu tiên bằng nhau. Không có gì được ghi ra và bộ nhớ duy nhất được dùng là hai biến đếm, nên cả hai quy tắc đều được đáp ứng. Với 10,001 giá trị và cả hai bản sao đều nằm gần cuối, cần khoảng 5 × 10^7 lần kiểm tra cặp.
Thuật toán
- Với mỗi vị trí
i, từ 0 đến cuối: - Với mỗi vị trí
jsaui, so sánhnums[i]vớinums[j]. - Trả về
nums[i]khi tìm thấy kết quả khớp đầu tiên.
def findDuplicate(nums):
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] == nums[j]:
return nums[i]
return -1 # unreachable: the input always holds a repeatTìm kiếm nhị phân theo giá trị
Ý tưởng
Tìm kiếm trong phạm vi các giá trị, không phải các vị trí. Với ngưỡng m, hãy đếm các phần tử có giá trị không lớn hơn m. Nếu số trùng lặp d lớn hơn m, mỗi giá trị từ 1 đến m xuất hiện nhiều nhất một lần, nên số lượng không vượt quá m. Nếu d không lớn hơn m, nhiều nhất n-m phần tử có giá trị lớn hơn m, nên có ít nhất m+1 phần tử có giá trị không lớn hơn m. Phép kiểm tra "count > m" cho kết quả sai khi giá trị nhỏ hơn d và đúng từ d trở lên, nên tìm kiếm nhị phân sẽ tìm ra m đầu tiên khiến phép kiểm tra đúng.
Trong ví dụ thứ hai, m = 2 đếm được 2 và 1, không quá 2 phần tử, còn m = 3 vẫn đếm được 2 phần tử, nên đáp án là 4. Mỗi lượt đọc mảng một lần: khoảng 14 lượt duyệt qua 10,001 giá trị.
Thuật toán
- Đặt
low= 1 vàhigh=n, độ dài củanumstrừ đi một. - Trong khi
low < high, lấymidở chính giữa hai giá trị. - Đếm các phần tử của
numscó giá trị không lớn hơnmid. - Nếu số lượng lớn hơn
mid, đặthigh=mid; nếu không, đặtlow=mid+1. - Trả về
low.
def findDuplicate(nums):
low, high = 1, len(nums) - 1
while low < high:
mid = (low + high) // 2
# How many values fall in 1..mid?
count = 0
for x in nums:
if x <= mid:
count += 1
if count > mid:
high = mid # 1..mid holds more values than it has room for
else:
low = mid + 1 # the repeat is above mid
return lowPhát hiện chu kỳ Floyd trên các liên kết giá trị
Ý tưởng
Hãy đọc mảng như các liên kết: vị trí i trỏ đến vị trí nums[i]. Có n+1 vị trí, mỗi vị trí có một liên kết, nên khi đi từ 0, ta sẽ quay lại một vị trí đã đi qua: một đoạn đuôi, rồi đến một vòng lặp. Ví dụ đầu tiên đi qua 0, 2, 1, rồi một vòng qua 5, 4.
Lối vào vòng lặp có thể được tiếp cận từ hai vị trí, một vị trí trên đoạn đuôi và một vị trí trong vòng lặp: ở đây là các vị trí 1 và 4, cả hai đều chứa 5. Không có giá trị nào bằng 0, nên vị trí 0 luôn nằm trên đoạn đuôi và lối vào luôn có hai đường đi vào. Chỉ có một giá trị lặp lại, nên lối vào chính là đáp án.
Giai đoạn 1 di chuyển slow một liên kết mỗi lượt và fast hai liên kết cho đến khi chúng gặp nhau, sau s lượt. fast đã đi thêm s bước, tương ứng với số vòng nguyên. Giai đoạn 2 đưa slow trở lại vị trí 0. Sau T bước, bằng độ dài đoạn đuôi, slow ở lối vào, còn fast ở vị trí mà một lượt đi từ 0 sẽ đến sau T bước cộng thêm số vòng nguyên: cũng là lối vào.
Thuật toán
- Xem mỗi vị trí
ilà một nút liên kết đến vị trínums[i], rồi đặt cả hai con trỏ tại vị trí 0. - Giai đoạn 1: di chuyển
slowđếnnums[slow]vàfastđếnnums[nums[fast]]cho đến khi chúng bằng nhau. - Giai đoạn 2: đặt lại
slowvề 0. - Di chuyển cả hai con trỏ mỗi lần một liên kết,
slowđếnnums[slow]vàfastđếnnums[fast], cho đến khi chúng bằng nhau. - Trả về vị trí đó: đó là giá trị bị lặp lại.
def findDuplicate(nums):
# Treat each index i as a node with one link, to nums[i].
# Phase 1: slow moves one link, fast moves two, until they meet in the cycle.
slow = fast = 0
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
# Phase 2: restart one pointer at index 0 and move both one link at a time.
# They meet at the cycle's entrance, the index two positions link to.
slow = 0
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow
Lỗi thường gặp và trường hợp biên
- Trả về điểm gặp nhau ở giai đoạn 1. Điểm này nằm đâu đó trên vòng lặp (loop): trong ví dụ đầu tiên, hai con trỏ (pointer) gặp nhau tại 4, nhưng đáp án là 5.
- Kiểm tra
slow == fasttrước khi di chuyển lần đầu. Cả hai đều bắt đầu ở 0, nên vòng lặp kết thúc ngay lập tức. - Bắt đầu đi từ vị trí khác 0. Vị trí 3 trong ví dụ đầu tiên liên kết với chính nó, tạo thành một vòng lặp không có lối vào, nên điểm vào đó không chứng minh được điều gì.
- Kiểm tra
count >= midtrong thuật toán tìm kiếm nhị phân (binary search). Khi không có giá trị nào từ 1 đếnmbị lặp hoặc bị thiếu, số lượng chính xác làm, nên chỉ có toán tử>mới phân chia được hai phía. - Đánh dấu các giá trị đã thấy bằng cách đổi dấu các phần tử hoặc hoán đổi các giá trị vào đúng vị trí. Cả hai cách đều tìm ra đáp án, nhưng đều làm thay đổi mảng (array).
Câu hỏi thường gặp3
Độ phức tạp thời gian của bài toán Tìm số trùng lặp là bao nhiêu?
Thuật toán phát hiện chu kỳ Floyd chạy trong thời gian O(n) với bộ nhớ bổ sung O(1). Tìm kiếm nhị phân trên các giá trị mất thời gian O(n log n) và bộ nhớ O(1), còn so sánh mọi cặp mất O(n²).
Tại sao không dùng tập hợp băm hoặc sắp xếp mảng?
Cả hai cách đều dùng được trong chương trình thực tế. Bài toán không cho phép dùng cách nào: tập hợp băm cần thêm bộ nhớ O(n), còn việc sắp xếp sẽ làm thay đổi nums hoặc cần một bản sao đầy đủ. Những quy tắc đó khiến bạn phải dùng góc nhìn vòng lặp.
Tại sao công thức tính tổng không hiệu quả với bài toán Tìm số trùng lặp?
Lấy tổng của mảng trừ đi 1 + 2 + ... + n chỉ cho ra giá trị trùng lặp khi giá trị đó xuất hiện đúng hai lần. Ở đây, một giá trị lặp lại có thể thay thế cho các giá trị bị thiếu: trong [4, 2, 4, 1, 4], hiệu là 15 trừ 10 = 5, một giá trị thậm chí không có trong mảng.
Bài tập tương tự
Các bài tập dùng cùng ý tưởng. Giải hai hoặc ba bài là bạn sẽ nhớ được mẫu này.
def findDuplicate(nums):
# Viết code tại đâyKiểm thử #1
Kiểm thử #2
Đối số
nums = [2, 5, 1, 3, 5, 4]
Đầu ra mong đợi
5