4. Median of Two Sorted Arrays

Vui lòng đọc hiểu đề trước khi đọc bài viết này tại đây:

https://leetcode.com/problems/median-of-two-sorted-arrays/description/

Table of Contents

1. Cách tiếp cận vấn đề

Hôm nay chúng ta sẽ cùng nhau giải quyết một bài toán khá thú vị và cũng là một câu hỏi phỏng vấn phổ biến ở các công ty lớn: "Median of Two Sorted Arrays". Đây là một bài toán mức độ "Hard" trên LeetCode, và dĩ nhiên việc tiếp cận nó từng bước một từ cách làm naive nhất, sau đó refactor từng bước để cải thiện time-complexity sẽ giúp chúng ta hiểu rõ được bản chất của vấn đề và cách áp dụng vào những bài toán tương tự.

Yêu cầu bài toán hết sức đơn giản, cho 2 mảng đã được sắp xếp tăng dần nums1 và nums2 với kích thước lần lượt là m và n. Trả về giá trị trung vị (KHÔNG phải trung bình) của 2 mảng đó với time-complexity O(log(m+n)).

Hay nói cách khác ta phải tìm giá trị trung vị của mảng được tạo từ 2 mảng nums1 và nums2 (vẫn phải duy trì thứ tự tăng dần).

• Ví dụ 1
• Input: nums1 = [1,3], nums2 = [2]
• Output: 2.00000

• Ví dụ 2
• Input: nums1 = [1,2], nums2 = [3,4]
• Output: 2.50000

Về cơ bản có thể thấy thì giá trị trung vị chính là giá trị nằm ở vị trí trung tâm của mảng sau khi được merge (0-based index):

• Nếu tổng chiều dài là một số lẻ
• Ví dụ:
• Input: nums1 = [1,3], nums2 = [2]
• Sau khi merge 2 mảng ta được: [1,2,3]
• Giá trị trung vị chính là giá trị ở vị trí = 1 và có giá trị là 2.0
• Nếu tổng chiều dài là một số chẵn
• Ví dụ:
• Input: nums1 = [1,2], nums2 = [3,4]
• Sau khi merge 2 mảng ta được: [1,2,3,4]
• Giá trị trung vị chính là giá trị trung bình cộng của 2 vị trí trung tâm là index 2 và 1 có giá trị là (2 + 3) / 2 = 2.5

Tuy nhiên, điểm khó ở chỗ nếu ta thực hiện việc merge trước rồi mới đi tìm trung vị thì time-complexity ít nhất phải là O(n + m), vì cần lần lượt duyệt qua tất cả các phần tử của 2 mảng. Như vậy đòi hỏi ta phải tiếp cận theo hướng Binary-Search với chiều dài khoảng tìm kiếm là từ index 0 đến (n+m) : [0, m + n) để có thể đạt được time-complexity là O(log(m+n)).

2. Solution & Phân Tích

Đầu tiên chúng ta sẽ tạm tưởng tượng và gọi mảng được gộp lại sau cùng từ 2 mảng nums1 và nums2 là nums. Ý tưởng chính là chúng ta sẽ "chia" mảng nums này thành hai phần: phần bên trái và phần bên phải. Mục tiêu là tìm ra một điểm chia trong mảng nums1 (gọi là partitionX) và một điểm chia trong mảng nums2 (gọi là partitionY) sao cho:

1. Tổng số lượng phần tử trong mảng gộp nums ở "phần bên trái" bằng tổng số lượng phần tử ở "phần bên phải".
2. Tất cả các phần tử trong mảng gộp nums ở "phần bên trái" đều nhỏ hơn hoặc bằng tất cả các phần tử ở "phần bên phải".

Khi tìm được điểm chia thỏa mãn hai điều kiện trên, số trung vị sẽ được xác định bởi các phần tử lớn nhất ở "phần bên trái" và các phần tử nhỏ nhất ở "phần bên phải".

Cụ thể hơn:

• maxLeftX: phần tử lớn nhất ở phần bên trái của nums1.
• minRightX: phần tử nhỏ nhất ở phần bên phải của nums1.
• maxLeftY: phần tử lớn nhất ở phần bên trái của nums2.
• minRightY: phần tử nhỏ nhất ở phần bên phải của nums2.

=> Chúng ta cần tìm partitionX và partitionY sao cho maxLeftX <= minRightY và maxLeftY <= minRightX.

Giá trị của số trung vị sẽ là:

• max(maxLeftX, maxLeftY) nếu tổng số phần tử là số lẻ
• (max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2 nếu tổng số phần tử là số chẵn

Note: Chúng ta có thể thực hiện tìm kiếm nhị phân trên mảng nhỏ hơn để tối ưu hóa thời gian chạy.

Time-Complexity: O(log(min(m, n))). Do thực hiện tìm kiếm nhị phân trên mảng nhỏ hơn trong hai mảng.
Space-Complexity: O(1). Không sử dụng thêm CTDL lưu trữ nào ngoài một vài biến để lưu các giá trị.

Với m và n lần lượt là kích thước của 2 mảng nums1 và nums2.

3. Code

Khi không tìm thấy các vị trí max, min, ta cần gán giá trị default cho nó để duy trì logic so sánh.

Nếu maxLeftX > minRightY thì điều này có nghĩa chúng ta đang lấy quá nhiều phần tử ở mảng nums1 góp vào "phần bên trái" của mảng gộp nums, cần giảm right, ngược lại cần tăng left.

© hieulm2k | Buy me a coffee