Array

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:

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

Minimum Size Subarray Sum

Minimum Window Substring

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: 

– Sort Colors 

Palindromic Substrings

– Merge Sorted Array

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: 

Daily Temperatures

– 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: 

– Merge Intervals

– Non-overlapping Intervals

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

– Minimum Size Subarray Sum

– 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: 

– First Missing Positive

– Daily Temperatures

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

Nâng cao

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é.

BeautyOnCode.

(ref)

Nếu bạn nghĩ những nội dung này là hữu ích, bạn có thể khích lệ mình bằng cách:

Mời mình ☕️ cafe qua Ko-fi hay Momo

Theo dõi 👀 để nhận các bài viết mới trên: Careerly, fanpage, linkedin

Subscribe channel Youtube BeautyOnCode giúp mình với! 

🤘 Nhắn mình nhé 🤘

Hẹn gặp mọi người một ngày nào đó!

Leave a Reply

Your email address will not be published. Required fields are marked *

RELATED POST

Cặp đôi hủy diệt code xấu: DRY và Orthogonality

Bạn có nghĩ giai đoạn bảo trì (maintenance) là sau khi chương trình được phát hành (release)? Và trong giai…

Nguyên tắc SOLID trong lập trình hướng đối tượng (OOP) – thực hành cùng ngôn ngữ Python

SOLID là gì? SOLID là 5 nguyên tắc nền tảng trong lập trình hướng đối tượng OOP (Object Oriented Programming), giúp…

Bốn bước để học và viết trong thời gian dài

Bài blog này mình muốn gửi đến 4 bước mình đã làm để có thể duy trì việc học và rèn luyện…

BeautyOnCode đạt top 1 trên Careerly

Time flies! Nhanh thật, vậy là mình đã đồng hành cùng các đọc giả trên Careerly được hơn 6 tháng,…

%d bloggers like this: