Longest Consecutive Sequence
Bạn nhận được một mảng (array) số nguyên nums không theo thứ tự cụ thể nào. Một dãy liên tiếp là nhóm các giá trị x, x+1, x+2 và cứ tiếp tục như vậy, trong đó mỗi giá trị đều xuất hiện ở đâu đó trong nums. Hãy trả về độ dài của dãy liên tiếp dài nhất. Giá trị xuất hiện nhiều lần chỉ được tính một lần.
Hàm
- numsinteger-array
- các số nguyên, theo thứ tự bất kỳ, có thể lặp lại
- Trả vềinteger
- độ dài của dãy giá trị liên tiếp dài nhất có trong nums
Ràng buộc
1 ≤ nums.length ≤ 104-109 ≤ nums[i] ≤ 109- Các giá trị có thể lặp lại. Vị trí trong mảng không quan trọng, chỉ cần biết những giá trị nào có mặt.
Ví dụ
- Đầu vào
- nums = [40, 4, 39, 1, 3, 2, 41]
- Đầu ra
- 4
- Giải thích
1,2,3và4đều có mặt, tạo thành một dãy gồm 4 giá trị, dù chúng nằm rải rác trong mảng. Dãy còn lại, từ39đến41, chỉ có 3 giá trị.
- Đầu vào
- nums = [7, 3, 7, 5, 6, 5]
- Đầu ra
- 3
- Giải thích
5,6và7tạo thành một dãy liên tiếp gồm 3 số.7thứ hai và5thứ hai không làm tăng thêm gì, còn3không thể nối vào vì thiếu4.
- Đầu vào
- nums = [10, 30, 20]
- Đầu ra
- 1
- Giải thích
- Không có hai giá trị nào chênh lệch nhau 1, nên mỗi đoạn chỉ chứa một giá trị và kết quả là 1.
Câu hỏi mở rộng
Giả sử các giá trị lần lượt được đưa vào và sau mỗi giá trị, bạn phải báo cáo đoạn liên tiếp dài nhất tính đến thời điểm đó. Bạn có thể luôn cập nhật đáp án trong thời gian trung bình O(1) cho mỗi giá trị không?
Gợi ý
Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.
Hãy thử từng giá trị làm số đầu tiên của một dãy rồi đếm tăng dần. Bạn hỏi đi hỏi lại câu hỏi nào, và mỗi câu trả lời tốn bao nhiêu khi bạn tìm giá trị đó trong mảng?
Câu hỏi là “
x+1có nằm trong mảng không?”. Tập hợp băm (hash set) trả lời câu hỏi này trong thời gian hằng số trung bình, đồng thời loại bỏ các phần tử trùng lặp.Chỉ bắt đầu đếm từ một giá trị
xmàx-1không có trong tập hợp. Từ đó, lần lượt đi đếnx+1,x+2và tiếp tục khi tập hợp có các giá trị đó, rồi giữ lại lượt đi dài nhất. Khi đó, mỗi giá trị chỉ được đi qua một lần.
Lời giải
Các giá trị của một dãy liên tiếp có thể nằm ở bất kỳ vị trí nào trong mảng. Việc sắp xếp đưa chúng về đúng thứ tự trong O(n log n). Tập hợp băm trả lời câu hỏi “có x+1 ở đây không?” trong O(1), và nếu bạn chỉ đếm từ những giá trị không có x-1, thì mỗi giá trị chỉ được duyệt qua một lần: tổng cộng O(n).
Đếm tăng từ mỗi giá trị bằng cách tìm kiếm trong mảng
Đúng, nhưng không chạy xong với các test lớn nhất
Ý tưởng
Xem mỗi giá trị là điểm bắt đầu tiềm năng của một dãy liên tiếp. Từ x, tìm trong mảng x+1, rồi đến x+2, cho đến khi không tìm thấy giá trị nào, sau đó ghi nhận số lượng lớn nhất. Mỗi dãy liên tiếp có một giá trị nhỏ nhất trong nums, và vòng lặp đi qua toàn bộ dãy đó bắt đầu từ giá trị này.
Mỗi lần tìm kiếm đọc tối đa n giá trị, và một dãy dài sẽ được duyệt lại từ mỗi phần tử của nó. Với 10^4 giá trị tạo thành một dãy đã xáo trộn, các lượt duyệt mất khoảng n²/2 = 5 × 10^7 bước, mỗi lượt quét trung bình một nửa mảng: khoảng 2.5 × 10^11 phép so sánh.
Thuật toán
- Đặt
bestbằng 0. - Với mỗi giá trị
starttrongnums, đặtcurrentbằngstartvàlengthbằng 1. - Trong khi quét
numsvẫn tìm thấycurrent+1, tăngcurrentvàlengththêm 1. - Lưu
lengthvàobestnếu nó lớn hơn giá trị hiện tại. - Trả về
best.
def longestConsecutive(nums):
best = 0
for start in nums:
current = start
length = 1
# "in" on a list reads it from the front until it finds the value.
while current + 1 in nums:
current += 1
length += 1
best = max(best, length)
return bestSắp xếp, rồi đếm các dãy liên tiếp
Ý tưởng
Sắp xếp đặt các giá trị thuộc cùng một dãy liên tiếp cạnh nhau: [40, 4, 39, 1, 3, 2, 41] trở thành [1, 2, 3, 4, 39, 40, 41], và các dãy được đọc từ trái sang phải.
Duyệt qua các giá trị đã sắp xếp và theo dõi độ dài của dãy hiện tại. Giá trị lớn hơn giá trị trước đó 1 đơn vị sẽ kéo dài dãy. Giá trị lặp lại không kéo dài cũng không kết thúc dãy, vì vậy hãy bỏ qua nó. Bất kỳ giá trị nào khác đều bắt đầu một dãy mới có độ dài 1.
Việc sắp xếp tốn O(n log n) và việc duyệt tốn O(n). Sắp xếp tại chỗ không cần mảng phụ; các ngôn ngữ sắp xếp bản sao sẽ dùng bộ nhớ O(n).
Thuật toán
- Sắp xếp
numstheo thứ tự tăng dần. - Đặt
bestvàrunthành 1 vì mảng không bao giờ rỗng. - Với mỗi chỉ số
ibắt đầu từ 1, bỏ quanums[i]nếu nó bằngnums[i-1]. - Nếu
nums[i]bằngnums[i-1]+1, cộng 1 vàorun; nếu không, đặtrunthành 1. Lưurunvàobestnếu nó lớn hơn. - Trả về
best.
def longestConsecutive(nums):
nums.sort()
best = 1
run = 1
for i in range(1, len(nums)):
if nums[i] == nums[i - 1]:
continue # a repeat neither extends nor breaks the run
if nums[i] == nums[i - 1] + 1:
run += 1
else:
run = 1
best = max(best, run)
return bestTập hợp băm, chỉ đếm từ đầu mỗi lần chạy
Ý tưởng
Với mỗi giá trị trong tập hợp băm, thao tác kiểm tra phần tử có thuộc tập hợp hay không có chi phí trung bình là O(1), còn các giá trị trùng lặp sẽ gộp thành một phần tử.
Duyệt từ mọi giá trị vẫn khiến bạn lặp lại công việc: trong dãy 1, 2, 3, 4, bạn sẽ đi 3 bước từ 1, 2 bước từ 2 và 1 bước từ 3. Vì vậy, chỉ bắt đầu duyệt từ giá trị đầu tiên của một dãy, tức là giá trị x mà x-1 không có trong tập hợp. Trong ví dụ 1, chỉ 1 và 39 thỏa mãn, tạo thành các dãy có độ dài 4 và 3.
Mỗi giá trị thuộc một dãy và chỉ bị duyệt qua trong lần duyệt của dãy đó, nên tổng số bước của tất cả các lần duyệt tối đa là n. Với một lần kiểm tra cho mỗi giá trị, tổng thời gian là O(n) và bộ nhớ dành cho tập hợp là O(n).
Thuật toán
- Đưa mọi giá trị của
numsvào tập hợp bămvalues, rồi đặtbestthành 0. - Với mỗi giá trị
xtrong tập hợp, bỏ qua nếux-1nằm trong tập hợp: đó không phải là giá trị đầu tiên của dãy. - Nếu không, đặt
endthànhxrồi tăng nó thêm 1 khiend+1nằm trong tập hợp. - Lưu
end-x+1vàobestnếu giá trị đó lớn hơn. - Trả về
best.
def longestConsecutive(nums):
values = set(nums)
best = 0
for value in values:
# Only a value with no left neighbour starts a run.
if value - 1 in values:
continue
end = value
while end + 1 in values:
end += 1
best = max(best, end - value + 1)
return best
Lỗi thường gặp và trường hợp biên
- Coi số lặp là khoảng trống hoặc là một bước sau khi sắp xếp. Trong
[1, 2, 2, 3], đặt lại độ dài dãy ở số2thứ hai thì được 2, còn tính số đó là một bước thì được 4. Đáp án là 3. - Đặt
bestbằng 0 trong lượt duyệt đã sắp xếp rồi chỉ cập nhật nó bên trong vòng lặp. Khi đó, mảng có một giá trị sẽ trả về 0 thay vì 1. - Duyệt từ mọi giá trị trong tập hợp thay vì chỉ từ đầu mỗi dãy. Khi đó, một dãy gồm
10^4giá trị sẽ tốn5 × 10^7bước. - Lặp qua
numsthay vì tập hợp. Nếu giá trị đầu tiên của một dãy gồm 2.500 phần tử xuất hiện 2.000 lần, bạn sẽ duyệt dãy đó 2.000 lần. - Dùng giá trị làm chỉ số của mảng. Các giá trị có thể lên đến
±10^9, nên mảng cần có2 × 10^9phần tử.
Câu hỏi thường gặp3
Độ phức tạp thời gian của Dãy con liên tiếp dài nhất là bao nhiêu?
Lời giải dùng tập hợp băm có thời gian chạy trung bình là O(n) và cần thêm O(n) bộ nhớ. Sắp xếp và đếm các lần chạy cần O(n log n). Nếu không dùng tập hợp, tìm kiếm trong mảng cho mỗi giá trị tiếp theo có thể mất đến O(n³).
Bạn có thể giải bài toán dãy liên tiếp dài nhất mà không cần thêm bộ nhớ không?
Có, nếu bạn có thể sắp xếp lại đầu vào: sắp xếp ngay tại chỗ rồi đếm các đoạn liên tiếp trong một lượt, bỏ qua các giá trị lặp lại. Cách này dùng bộ nhớ phụ O(1) nhưng mất thời gian O(n log n). Lời giải có độ phức tạp O(n) cần dùng tập hợp băm.
Union-find có thể giải bài toán dãy liên tiếp dài nhất không?
Có. Hãy tạo một tập hợp cho mỗi giá trị riêng biệt, nối x với x+1 bất cứ khi nào cả hai đều có mặt, rồi trả về kích thước của tập hợp lớn nhất. Cách này chạy gần với thời gian O(n), nhưng cần một bản đồ ánh xạ giá trị sang chỉ số, các liên kết cha và kích thước, trong khi cách duyệt tập hợp băm chỉ cần một tập hợp.
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 longestConsecutive(nums):
# Viết code ở đâyKiểm thử #1
Kiểm thử #2
Kiểm thử #3
Đối số
nums = [40, 4, 39, 1, 3, 2, 41]
Đầu ra mong đợi
4