Vui lòng đọc hiểu đề trước khi đọc bài viết này tại đây:
https://leetcode.com/problems/contains-duplicate/
Table of Contents
1. Cách tiếp cận vấn đề
❗Điều cần lưu ý đầu tiên là output của bài toán chỉ cần trả về boolean đại diện cho việc mảng có chứa phần tử bị duplicate hay không,
- Điều đó cũng có nghĩa là bất kỳ khi nào tìm được 1 phần tử bị duplicate, chúng ta có thể break ra khỏi flow và trả về kết quả ngay lập tức ✅
- Và sau cùng, nếu không tìm được phần tử nào như vậy thì có thể kết luận mảng không chứa phần tử bị duplicate ❌
Đây là 1 trong những bài toán có thể nói là dễ nhất trong phần Array, tuy nhiên đối với những bài dễ như vậy sẽ có rất nhiều cách làm và cách tiếp cận khác nhau, chung quy lại sẽ có 2 cách tiếp cận chính: Tối ưu không gian bộ nhớ (space complexity) hay tối ưu về thời gian chạy (time complexity).
Vì cuộc đời không như mơ, nếu tối ưu về bộ nhớ thì chúng ta phải chấp nhận nó chạy chậm hơn 1 chút, và ngược lại nếu muốn chạy nhanh hơn thì cần sử dụng thêm bộ nhớ, sẽ rất khó để tối ưu cả 2 cùng 1 lúc. Và khái niệm hay đuợc dùng để diễn đạt cho điều này chính là: Trade-Off
2. Solution & Phân Tích
2.1. Tối ưu bộ nhớ
2.1.1. Brute Force
Để tối ưu bộ nhớ, chúng ta sẽ không sử dụng thêm bất kỳ bộ nhớ nào ngoài mảng input nums. Điều đó có nghĩa là để kiểm tra 1 phần tử có bị duplicate hay không, hay có xuất hiện từ 2 lần trở lên hay không, thì ta cần 2 vòng for loop để làm điều đó, kỹ thuật này còn gọi là vét cạn (Brute Force, quét qua mọi trường hợp có thể xảy ra đến khi tìm được kết quả mong muốn)
- Vòng for đầu tiên dùng để cố định qua từng phần tử trong mảng, tạm gọi con trỏ vị trí là i
- Vòng for thứ hai sẽ đi qua các phần tử ở sau vị trí i (i + 1), tạm gọi là con trỏ j, và nếu có bất kỳ vị trí j nào mà tại đó xuất hiện 1 phần tử bằng với phần tử mà ta đã cố định ở vòng lặp đầu tiên, thì có thể kết luận mảng này chứa phần tử bị duplicate và trả về true, kết thúc hàm.
- Sau cùng nếu không tìm được phần tử nào bị trùng, trả về false, kết thúc hàm.
Space Complexity: O(1)
Time Complexity: O(n^2)
n: số lượng phần tử của mảng
2.1.2. Sorting
Đây là 1 cách tối ưu hơn vét cạn 1 xíu, idea là chúng ta sẽ gom các phần tử giống nhau lại gần nhau hơn, và để làm được điều đó thì chúng ta có thể sắp xếp mảng theo thứ tự nào cũng được, rồi dùng 1 vòng lặp để kiểm tra xem có 2 phần tử liền kề nào giống nhau hay không, nếu có thì trả về true và kết thúc hàm, sau cùng nếu không tìm được phần tử nào bị trùng, trả về false, kết thúc hàm.
Space Complexity: O(1)
Time Complexity: O(nlogn) - Sorting nên thời gian tối ưu nhất là nlogn
n: số lượng phần tử của mảng
2.2. Tối ưu thời gian
Sử dụng thêm bộ nhớ, chấp nhận hi sinh để đánh đổi về mặt thời gian chính là kim chỉ nam cho cách làm này.
Vậy câu hỏi đặt ra là ta sẽ chọn cấu trúc dữ liệu nào để rút gọn từ 2 vòng for thành còn 1 vòng for? Làm sao có thể vừa duyệt vừa kiểm tra phần tử đó đã xuất hiện trong mảng hay chưa?
2.2.1. Map
Map là kiểu cấu trúc dữ liệu dạng key-value, ta sẽ dùng nó để lưu mảng với key là giá trị của phần tử, và value là số lần xuất hiện của nó.
Ở mỗi lần duyệt, ta sẽ kiểm tra xem phần tử hiện tại đã xuất hiện trước đó bao giờ chưa, bằng việc kiểm tra số lần xuất hiện trước đó của nó (thao tác kiểm tra là get value của phần tử từ map chỉ tốn O(1))
- Nếu lớn hơn hoặc bằng 1 thì chứng tỏ đã tồn tại phần tử này trong mảng rồi, trả về true và kết thúc hàm.
- Ngược lại chứng tỏ đây là lần đầu tiên ta gặp phần tử này, tăng biến đếm lên 1 và cập nhật giá trị của phần tử hiện tại ở map.
Space Complexity: O(n)
Time Complexity: O(n)
n: số lượng phần tử của mảng
2.1.2. Set
Set là cấu trúc dữ liệu chỉ chứa các phần tử duy nhất, và với đa số các ngôn ngữ lập trình, nó đều hỗ trợ phương thức để kiểm tra xem phần tử đó đã tồn tại trong Set hay chưa (đằng sau nó cũng sử dụng Hash Table như Map nên thao tác này chỉ tốn O(1)). Tận dụng điều đó ta có được flow như sau, về cơ bản là cũng giống như map:
Ở mỗi lần duyệt, ta sẽ dùng method có sẵn của set để kiểm tra phần tử hiện tại:
- Nếu đã tồn tại, trả về true và kết thúc hàm.
- Nếu chưa tồn tại, thêm phần tử đó vào trong Set.
Space Complexity: O(n)
Time Complexity: O(n)
n: số lượng phần tử của mảng
3. Code
Mình sẽ sử dụng ngôn ngữ Java và cấu trúc dữ liệu Set để minh hoạ. Vì method add trong Java sẽ trả về false nếu phần tử đã tồn tại trước đó và ngược lại, nên ta không cần dùng thêm method contains để kiểm tra sự tồn tại của phần tử nữa, nói chung là 1 công đôi việc.
