Bài 4 Leetcode: Median of Two Sorted Arrays

Đề bài:

Cho hai mảng đã được sắp xếp nums1 và nums2 với kích thước lần lượt là m và n, hãy trả về trung vị của hai mảng đã được sắp xếp. Độ phức tạp thời gian chạy tổng thể của thuật toán nên là O(log (m+n)).

Ví dụ 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Giải thích: Mảng đã được hợp nhất là [1,2,3] và trung vị là 2.

Ví dụ 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Giải thích: Mảng đã được hợp nhất là [1,2,3,4] và trung vị là (2 + 3) / 2 = 2.5.

Ràng buộc:

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -10⁶ <= nums1[i], nums2[i] <= 10⁶

Giải thích thuật toán bằng C++

class Solution {
 public:
  double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    const int n1 = nums1.size();
    const int n2 = nums2.size();
    if (n1 > n2)
      return findMedianSortedArrays(nums2, nums1);

    int l = 0;
    int r = n1;

    while (l <= r) {
      const int partition1 = (l + r) / 2;
      const int partition2 = (n1 + n2 + 1) / 2 - partition1;
      const int maxLeft1 = partition1 == 0 ? INT_MIN : nums1[partition1 - 1];
      const int maxLeft2 = partition2 == 0 ? INT_MIN : nums2[partition2 - 1];
      const int minRight1 = partition1 == n1 ? INT_MAX : nums1[partition1];
      const int minRight2 = partition2 == n2 ? INT_MAX : nums2[partition2];
      if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1)
        return (n1 + n2) % 2 == 0
                   ? (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) * 0.5
                   : max(maxLeft1, maxLeft2);
      else if (maxLeft1 > minRight2)
        r = partition1 - 1;
      else
        l = partition1 + 1;
    }

    throw;
  }
};

Đoạn mã trên triển khai thuật toán để tìm trung vị của hai mảng đã được sắp xếp. Dưới đây là giải thích chi tiết về cách thuật toán hoạt động:

1. Kiểm tra số phần tử trong mảng nums1 và nums2 (lần lượt là n1 và n2).
2. Nếu n1 > n2, hoán đổi vị trí của nums1 và nums2 để đảm bảo rằng mảng nums1 có ít phần tử hơn.
3. Khởi tạo hai biến l và r, lần lượt là chỉ số bắt đầu và kết thúc của mảng nums1 trong quá trình tìm kiếm.
4. Bắt đầu một vòng lặp while trong đó l là chỉ số bắt đầu và r là chỉ số kết thúc của mảng nums1.
5. Trong mỗi vòng lặp, tính toán vị trí chia mảng 1 (partition1) và mảng 2 (partition2) bằng cách sử dụng công thức (n1 + n2 + 1) / 2 – partition1.
6. Xác định các giá trị lớn nhất bên trái (maxLeft1 và maxLeft2) và giá trị nhỏ nhất bên phải (minRight1 và minRight2) của hai mảng tại vị trí chia tương ứng.
7. Kiểm tra điều kiện maxLeft1 <= minRight2 và maxLeft2 <= minRight1. Nếu điều kiện này được thỏa mãn, ta đã tìm được vị trí chia mảng đúng và trả về trung vị tương ứng.
8. Nếu maxLeft1 > minRight2, điều này cho thấy rằng vị trí chia mảng của nums1 cần được di chuyển sang trái (giảm r). Ngược lại, nếu maxLeft2 > minRight1, vị trí chia mảng của nums1 cần được di chuyển sang phải (tăng l).
9. Lặp lại quá trình từ bước 5 đến bước 8 cho đến khi tìm được vị trí chia mảng đúng hoặc kết thúc vòng lặp.
10. Nếu không tìm thấy vị trí chia mảng đúng sau khi kết thúc vòng lặp, ném một ngoại lệ.
11. Trả về trung vị tương ứng.

Thuật toán này sử dụng phương pháp tìm kiếm nhị phân để xác định vị trí chia mảng sao cho mảng con bên trái chứa các phần tử nhỏ hơn mảng con bên phải. Kết hợp với việc xử lý các trường hợp đặc biệt khi mảng có số phần tử là chẵn hay lẻ, thuật toán đảm bảo độ phức tạp thời gian chạy tổng thể là O(log (m+n)).

Giải thích thuật toán bằng Java

class Solution {
  public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    final int n1 = nums1.length;
    final int n2 = nums2.length;
    if (n1 > n2)
      return findMedianSortedArrays(nums2, nums1);

    int l = 0;
    int r = n1;

    while (l <= r) {
      final int partition1 = (l + r) / 2;
      final int partition2 = (n1 + n2 + 1) / 2 - partition1;
      final int maxLeft1 = partition1 == 0 ? Integer.MIN_VALUE : nums1[partition1 - 1];
      final int maxLeft2 = partition2 == 0 ? Integer.MIN_VALUE : nums2[partition2 - 1];
      final int minRight1 = partition1 == n1 ? Integer.MAX_VALUE : nums1[partition1];
      final int minRight2 = partition2 == n2 ? Integer.MAX_VALUE : nums2[partition2];
      if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1)
        return (n1 + n2) % 2 == 0
            ? (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) * 0.5
            : Math.max(maxLeft1, maxLeft2);
      else if (maxLeft1 > minRight2)
        r = partition1 - 1;
      else
        l = partition1 + 1;
    }

    throw new IllegalArgumentException();
  }
}

Giải thích thuật toán bằng Python

class Solution:
  def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
    n1 = len(nums1)
    n2 = len(nums2)
    if n1 > n2:
      return self.findMedianSortedArrays(nums2, nums1)

    l = 0
    r = n1

    while l <= r:
      partition1 = (l + r) // 2
      partition2 = (n1 + n2 + 1) // 2 - partition1
      maxLeft1 = -2**31 if partition1 == 0 else nums1[partition1 - 1]
      maxLeft2 = -2**31 if partition2 == 0 else nums2[partition2 - 1]
      minRight1 = 2**31 - 1 if partition1 == n1 else nums1[partition1]
      minRight2 = 2**31 - 1 if partition2 == n2 else nums2[partition2]
      if maxLeft1 <= minRight2 and maxLeft2 <= minRight1:
        return (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) * 0.5 if (n1 + n2) % 2 == 0 else max(maxLeft1, maxLeft2)
      elif maxLeft1 > minRight2:
        r = partition1 - 1
      else:
        l = partition1 + 1