Array là gì?
Mảng (array) là kiểu dữ liệu phổ biến nhất, câu hỏi về mảng thường là quan trọng trong các cuộc phỏng vấn về kỹ thuật dành cho lập trình viên.
Ưu điểm:
Mảng (array) cho phép:
– lưu nhiều phần tử vào một biến duy nhất.
– truy cập các phần tử trong mảng với index (chỉ mục).
Nhược điểm:
– thay đổi các phần tử trong mảng diễn ra chậm hơn linked list khi thay đổi các phần tử giữa mảng vì các phần tử còn lại sẽ phải di chuyển để phù hợp với vị trí mới sau khi đã thêm / xóa.
– một số ngôn ngữ yêu cầu kích thước mảng cần khai báo trước và không thể thay đổi sau khi đã khởi tạo. Nếu phần tử được thêm vào vượt quá kích thước mảng thì việc sao chép lại mảng cũ và thêm mảng mới làm tốn thời gian là O(n).
Một số nguồn học về mảng
– Course “array data structure” – Guru99
– Video “Arrays” – University of California San Diego
Một số khái niệm liên quan đến mảng
– “Subarray” là mảng con chứa các phần tử giữ nguyên vị trí liền kề trong mảng.
– “Subsequence” là một dãy các phần tử tạo ra bằng cách xóa một hay nhiều các phần tử khác nhưng vẫn giữ nguyên thứ tự trong mảng.
Ví dụ: arr = [1, 2, 3, 4, 5, 6]
– thì [1, 2, 3] là subarray, nhưng [1, 4, 5] không phải là subarray
– thì [1, 4, 5] là subsequence, nhưng [1, 4, 3] không phải là subsequence
Độ phức tạp của một số thao tác trên mảng
– truy cập một phần tử – O(1)
– tìm kiếm trên mảng – O(n)
– tìm kiếm trên mảng đã được sắp xếp – O(log(n))
– chèn / xóa một phần tử vào mảng (ví trí đầu, cuối) – O(1)
– chèn / xóa một phần tử vào mảng (ví trí giữa) – O(n)
Một số lưu ý khi phân tích bài toán về mảng
– Làm rõ nếu cho phép các phần tử được phép trùng nhau
– Cẩn thận khi sử dụng index, vì nếu index vượt quá độ dài của mảng sẽ gây lỗi
– Cắt / nối mảng sẽ có thời gian O(n)
– Một số trường hợp đặc biệt:
– Mảng rỗng
– Mảng / subarray / subsequence chỉ có 1, 2 phần tử
– Mảng có các phần tử trùng nhau
Các kỹ thuật giải bài toán với mảng
Sliding window
Kỹ thuật này thường sử dụng hai con trỏ (two pointers) trượt cùng hướng và không bao giờ vượt nhau. Điều này đảm bảo mỗi giá trị được truy cập nhiều nhất 2 lần, và có độ phức tạp O(n)
**Luyện tập: **
– Longest Substring Without Repeating Characters
Two pointers
Hai con trỏ là kỹ thuật tổng quát hơn của “Sliding window”, với hai con trỏ và có thể cắt nhau hay có thể nằm trên hai mảng khác nhau.
**Luyện tập: **
Traversing from the right
Đôi khi cần duyệt mảng từ bên phải để giải quyết bài toán
**Luyện tập: **
– Number of Visible People in a Queue
Sorting the array
Đôi khi việc sắp xếp mảng theo một thứ tự nhất định giúp giải quyết vấn đề nhanh hơn. Nếu một mảng đã sắp xếp, hay một phần mảng đã sắp xếp có thể áp dụng binary search (tìm kiếm nhị phân) để giải quyết bài toán với thời gian nhỏ hơn O(n)
**Luyện tập: **
Precomputation
Với các bài toán cần tính toán (tổng, nhân, …) thì việc tính toán trước (có thể với các subarray hay subsequence) sẽ giúp giải bài toán dễ dàng hơn.
**Luyện tập: **
– Product of Array Except Self
– LeetCode questions tagged “prefix-sum”
Index as a hash key
Nếu bạn được giao một mảng nhưng yêu cầu thời gian O(1), bạn có thể sử dụng chính mảng đó như một mảng băm (khóa băm) để giải.
**Luyện tập: **
Traversing the array more than once
Đôi khi bạn cần duyệt qua mảng với một số lần nhất định để giải quyết bài toán. Và việc duyệt qua mảng với một số lần nhất định thì thuật toán của bạn vẫn có độ phức tạp là O(n).
Một số bài toán
Cơ bản
– Two Sum
– Best Time to Buy and Sell Stock
– Product of Array Except Self
Nâng cao
– Search in Rotated Sorted Array
– 3Sum
Trên đây là các nội dung giúp các bạn học về kiểu cấu trúc dữ liệu mảng.
Hi vọng bạn sẽ hiểu thêm mảng, rất quen thuộc và cũng rất thú vị.
À, mình có một repo nơi giải leetcode hàng tuần, bạn thích thì có thể tham gia nhé.
Bài viết gốc nằm ở blog cá nhân của mình, mời bạn ghé chơi.
BeautyOnCode.
Nguồn: viblo.asia