Vui lòng đọc hiểu đề trước khi đọc bài viết này tại đây:
https://leetcode.com/problems/longest-consecutive-sequence/description/
Table of Contents
1. Cách tiếp cận vấn đề
Đầu tiên, ta cần làm rõ yêu cầu của đề bài: tìm ra chuỗi liên tiếp dài nhất trong một mảng, liên tiếp ở đây không có nghĩa là nó xuất hiện liên tiếp liền kề nhau, cũng không có nghĩa là nó phải theo thứ tự tăng dần hay giảm dần, các con số có thể nằm rải rác, miễn sao khi ta ghép chúng ta với nhau sẽ hình thành nên được một chuỗi với các số liên tiếp nhau, và chuỗi đó phải là dài nhất.
Ví dụ: với input nums = [100,4,200,1,3,2] thì ta sẽ được output là 4, vì chuỗi liên tiếp dài nhất là [1, 2, 3, 4]
Một lưu ý quan trọng là ta cần giải bài toán với độ phức tạp thời gian là O(n) - Điều này ngăn chặn việc ta sắp xếp lại các phần tử và đếm các phần tử liên tiếp, buộc ta phải sử dụng thêm bộ nhớ ngoài (trade off) kết hợp với giải thuật hợp lý để có thể giải bài toán trong độ phức tạp thời gian cho phép.
Note: Bộ nhớ ngoài ở đây là một data structure nào đó phù hợp với bài toán.
Ta có thể bắt đầu bằng việc liên kết các tính chất trong một chuỗi liên tiếp trước:
- Khi xét một số bất kỳ là a, nếu số đó nằm trong một chuỗi nào đó thì phải tồn tại a - 1 hoặc a + 1 ở trong chuỗi đó, còn nếu không thì số a đang xét chính là một số đơn lẻ và không thuộc bất kỳ chuỗi nào.
- Mỗi chuỗi số thì luôn luôn phải có 2 cận/biên trái và phải, điều này sẽ hữu ích nếu ta muốn duy trì một tính chất nào đó lên chuỗi số đó, thì ta chỉ cần cho 2 biên trái và phải giữ đúng giá trị của tính chất đó, và nó sẽ đại diện cho toàn bộ các phần tử trong chuỗi đó. Ví dụ: khi xếp hàng các học sinh nam và nữ, ta chỉ cần nhìn vào đầu hàng hoặc cuối hàng là đã có thể xác định được dãy đó là nam hay là nữ.
Vậy quay về bài toán ban đầu, những điều ta cần phải giải quyết để giải được bài toán là:
- Tìm ra được một data structure phù hợp
- Áp dụng được 2 tính chất đã nêu của một chuỗi số để tìm ra chuỗi liên tiếp dài nhất
2. Solution & Phân Tích
Đối với các bài toán đếm như thế này, thì không có cấu trúc dữ liệu nào tuyệt vời hơn Map, nó sẽ giúp ta lưu trữ lại theo dạng key - value và hỗ trợ 1 số thao tác với độ phức tạp chỉ O(1).
Áp dụng vào bài toán đã nêu, ta sẽ dùng Map để lưu key chính là các con số num ở trong mảng đã cho, và value sẽ là số lượng các phần tử liên tiếp nếu num là biên trái hoặc phải của một chuỗi.
Ta sẽ duyệt qua lần lượt các phần tử num trong mảng input nums đã cho:
- Nếu phần tử num chưa được process
- Ta sẽ kì vọng số num này: (ví dụ với num = 5)
- Có thể là biên trái mới của một chuỗi có sẵn: nếu trước đó ta có chuỗi 6,7,8,...
- Có thể là biên phải mới của một chuỗi có sẵn: nếu trước đó ta có chuỗi ..,2,3,4
- Hay đẹp hơn là ở giữa, nối giữa hai chuỗi có sẵn: ...2,3,4 và 6,7,8,...
- Chính từ kì vọng đó, ta cần tìm ra các số num - 1 (số bên trái num và là biên phải hiện tại), num + 1 (số bên phải num và là biên trái hiện tại) có tồn tại trong mảng hay không, nếu có thì ta sẽ lấy ra số lượng các phần tử liên tiếp hiện tại mà các biên đó đang nắm giữ tạm gọi là leftLength và rightLength.
- Còn số num thì chiều dài của num luôn bằng 1 do ta chỉ xét nó đúng một lần và có thể tạm coi số num chính là biên trái và biên phải trong chuỗi chỉ chứa chính nó. Bây giờ do ta đã tìm được leftLength và rightLength rồi, nên ta cần cập nhật lại chiều dài mới = leftLength + rightLength + 1.
- Sau khi tính được chiều dài mới, ta có 2 việc cần phải làm:
- So sánh và cập nhật lại giá trị max hiện tại
- Cập nhật lại giá trị cho 2 biên của số num với giá trị của chiều dài mới này.
- Biên trái = num - leftLength
- Biên phải = num + rightLength
- Nếu phần tử num đã được process, ta có thể skip qua nó để tránh phải tính toán lại dẫn đến sai kết quả.
- Sau khi duyệt qua hết tất cả phần tử, trả về giá trị max chính là chiều dài của chuỗi liên tiếp dài nhất.
Time-Complexity: O(n) - Mỗi phần tử chỉ duyệt qua 1 lần
Space-Complexity: O(n)
Với n là số lượng các phần tử trong mảng input nums
3. Code
Mình sẽ sử dụng code Java để minh hoạ:
