Median of Two Sorted Arrays

Q: Độ phức tạp thời gian của bài toán tìm trung vị của hai mảng đã sắp xếp là bao nhiêu?

Tìm kiếm nhị phân trên vị trí cắt mất thời gian O(log(min(m, n))) và không gian O(1) , vì mỗi bước giảm một nửa số vị trí cắt có thể trong danh sách ngắn hơn. Việc trộn mất thời gian O(m + n) : với hai danh sách có 3000 phần tử, cần khoảng 12 bước thay vì 6000.

Q: Tại sao tìm kiếm nhị phân trên mảng ngắn hơn?

Vì j = half-i . Khi i nằm trong phạm vi của danh sách ngắn hơn, j luôn nằm trong khoảng từ 0 đến độ dài của danh sách dài hơn, vì vậy mọi lần đọc đều nằm trong phạm vi hoặc vượt qua một đầu danh sách mà bạn xem như vô cực.

KhóTìm kiếm nhị phân

+10

Bạn nhận được hai danh sách số nguyên, nums1 và nums2, mỗi danh sách được sắp xếp từ nhỏ đến lớn và có ít nhất một giá trị. Hãy trả về trung vị của tất cả giá trị trong hai danh sách, dưới dạng văn bản.

Nếu tổng số phần tử là số lẻ, trung vị là giá trị ở giữa, chẳng hạn như "4". Nếu tổng số phần tử là số chẵn, trung vị là trung bình của hai giá trị ở giữa, chẳng hạn như "2.5" hoặc "-0.5". Viết số nguyên không có dấu thập phân và viết số không là "0", không bao giờ viết "-0". Hướng đến độ phức tạp thời gian O(log(min(m, n))).

Hàm

findMedianSortedArrays(nums1: integer-array, nums2: integer-array) → string

nums1integer-array: danh sách đầu tiên, được sắp xếp từ nhỏ nhất đến lớn nhất
nums2integer-array: danh sách thứ hai, được sắp xếp từ nhỏ nhất đến lớn nhất
Trả vềstring: trung vị của tất cả các giá trị, dưới dạng văn bản như "4" hoặc "-2.5"

Ràng buộc

1 ≤ nums1.length, nums2.length ≤ 3000
-10⁶ ≤ nums1[i], nums2[i] ≤ 10⁶
Cả hai danh sách đều được sắp xếp theo thứ tự không giảm, và các giá trị có thể lặp lại.

Ví dụ

Đầu vào: nums1 = [1, 4]nums2 = [2, 7, 9]
Đầu ra: "4"
Giải thích: Kết hợp lại, các giá trị là 1, 2, 4, 7, 9. Có năm giá trị nên có một giá trị ở giữa, là giá trị thứ ba, bằng 4.

Câu hỏi mở rộng

Bạn có thể dùng cách chia tương tự để tìm giá trị nhỏ thứ k trong hai danh sách, với mọi k, trong thời gian logarit không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Gộp các danh sách sẽ cho ta trung vị trong O(m + n), nhưng hầu hết giá trị mà thuật toán đọc không thể làm thay đổi đáp án. Trung vị chỉ phụ thuộc vào vị trí đường cắt giữa nửa dưới và nửa trên, và chỉ cần một con số để xác định đường cắt đó: số lượng giá trị lấy từ danh sách ngắn hơn vào nửa dưới. Tìm kiếm nhị phân sẽ tìm ra con số này trong O(log(min(m, n))) bước.

Gộp hai danh sách

Ý tưởng

Trộn các danh sách như thuật toán sắp xếp trộn, thành một danh sách đã sắp xếp merged. Với total = m + n, hãy cộng merged[(total-1)/2] và merged[total/2], dùng phép chia lấy phần nguyên. Nếu tổng là số lẻ, cả hai đều là giá trị ở giữa; nếu tổng là số chẵn, chúng là hai giá trị ở giữa. Vì vậy, trong cả hai trường hợp, một nửa tổng là trung vị.

Ngay cả khi dừng ở giữa, các bước trộn vẫn xử lý hơn một nửa số giá trị, nên độ phức tạp thời gian là O(m + n).

Thuật toán

Gộp các danh sách vào merged, luôn lấy giá trị hiện tại nhỏ hơn, rồi đến phần còn lại của danh sách chưa hết.
Với total = m + n, cộng merged[(total-1)/2] và merged[total/2].
Trả về một nửa tổng dưới dạng văn bản: chia tổng chẵn cho 2; với tổng lẻ, viết dấu, một nửa giá trị tuyệt đối và .5.

def half_text(total):
    # total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
    if total % 2 == 0:
        return str(total // 2)
    sign = "-" if total < 0 else ""
    return sign + str(abs(total) // 2) + ".5"


def findMedianSortedArrays(nums1, nums2):
    # Merge the two sorted lists into one, the way merge sort does.
    merged = []
    i = j = 0
    while i < len(nums1) and j < len(nums2):
        if nums1[i] <= nums2[j]:
            merged.append(nums1[i])
            i += 1
        else:
            merged.append(nums2[j])
            j += 1
    merged.extend(nums1[i:])
    merged.extend(nums2[j:])
    total = len(merged)
    # For an odd total both indexes point at the one middle value.
    return half_text(merged[(total - 1) // 2] + merged[total // 2])

Tìm kiếm nhị phân trên điểm cắt

Ý tưởng

Cho nửa dưới chứa half = (m+n+1)/2 giá trị, nhiều hơn một giá trị nếu tổng là số lẻ. Nửa dưới lấy i giá trị từ đầu nums1 và j = half-i giá trị từ đầu nums2. Vị trí cắt đúng khi không có giá trị nào ở phía dưới lớn hơn bất kỳ giá trị nào ở phía trên. Mỗi danh sách đã được sắp xếp, nên chỉ cần kiểm tra hai điều kiện: left1 ≤ right2 và left2 ≤ right1, trong đó left là giá trị cuối cùng một danh sách đưa vào nửa dưới, còn right là giá trị đầu tiên danh sách giữ lại. Nếu một phía không có giá trị, hãy xem giá trị đó là âm hoặc dương vô cực.

Nếu left1 > right2, i quá lớn; nếu left2 > right1, i quá nhỏ. Vì vậy, ta tìm kiếm nhị phân i trong khoảng từ 0 đến m. Với [1, 2] và [3, 4], i = 1 không thỏa mãn vì left2 = 3 > right1 = 2, còn i = 2 thỏa mãn: (2 + 3) / 2 = 2.5.

Thuật toán

Đảm bảo nums1 là danh sách ngắn hơn; đặt half = (m+n+1)/2.
Tìm kiếm nhị phân i từ lo = 0 đến hi = m, với j = half-i.
Đọc left1 = nums1[i-1], right1 = nums1[i], left2 = nums2[j-1] và right2 = nums2[j], dùng vô cực khi vượt qua điểm cuối.
Nếu left1 > right2, đặt hi = i-1. Nếu left2 > right1, đặt lo = i+1.
Nếu không, với tổng lẻ, trả về max(left1, left2). Với tổng chẵn, lấy max(left1, left2) + min(right1, right2) chia đôi, biểu diễn dưới dạng văn bản.

def half_text(total):
    # total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
    if total % 2 == 0:
        return str(total // 2)
    sign = "-" if total < 0 else ""
    return sign + str(abs(total) // 2) + ".5"


def findMedianSortedArrays(nums1, nums2):
    # Binary search over the shorter list.
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1
    m, n = len(nums1), len(nums2)
    half = (m + n + 1) // 2   # size of the left half; it gets the extra value when m + n is odd
    lo, hi = 0, m
    while lo <= hi:
        i = (lo + hi) // 2    # values the left half takes from nums1
        j = half - i          # values it takes from nums2
        # An empty side counts as minus or plus infinity.
        left1 = nums1[i - 1] if i > 0 else float("-inf")
        right1 = nums1[i] if i < m else float("inf")
        left2 = nums2[j - 1] if j > 0 else float("-inf")
        right2 = nums2[j] if j < n else float("inf")
        if left1 > right2:
            hi = i - 1        # too many values from nums1
        elif left2 > right1:
            lo = i + 1        # too few values from nums1
        else:
            left_max = max(left1, left2)
            if (m + n) % 2 == 1:
                return str(left_max)
            return half_text(left_max + min(right1, right2))
    return ""  # not reached: sorted input always has a valid split

Lỗi thường gặp và trường hợp biên

Lấy trung bình bằng số thực. Python in số trung vị nguyên thành 3.0, còn %f của C in 2.5 thành 2.500000. Hãy giữ tổng là số nguyên.
Viết thương nguyên rồi thêm .5 khi tổng là số lẻ âm. -1 / 2 cho kết quả 0 trong C và Java, nên -0.5 thành 0.5; -5 // 2 cho kết quả -3 trong Python, nên -2.5 thành -3.5. Hãy chia đôi giá trị tuyệt đối rồi thêm lại dấu.
Viết -0. Hai giá trị ở giữa là -1 và 1, tổng bằng 0, nên đáp án là "0". Hãy lấy dấu từ tổng.
Tìm kiếm trong danh sách dài hơn. j = half-i có thể nhỏ hơn 0 hoặc vượt quá n. Hãy đổi chỗ hai danh sách trước.
Đọc nums1[i-1] khi i = 0, như với [9] và [1, 2]. Hãy dùng vô cực cho các giá trị còn thiếu.

Câu hỏi thường gặp3

Độ phức tạp thời gian của bài toán tìm trung vị của hai mảng đã sắp xếp là bao nhiêu?

Tìm kiếm nhị phân trên vị trí cắt mất thời gian O(log(min(m, n))) và không gian O(1), vì mỗi bước giảm một nửa số vị trí cắt có thể trong danh sách ngắn hơn. Việc trộn mất thời gian O(m + n): với hai danh sách có 3000 phần tử, cần khoảng 12 bước thay vì 6000.

Tại sao tìm kiếm nhị phân trên mảng ngắn hơn?

Vì j = half-i. Khi i nằm trong phạm vi của danh sách ngắn hơn, j luôn nằm trong khoảng từ 0 đến độ dài của danh sách dài hơn, vì vậy mọi lần đọc đều nằm trong phạm vi hoặc vượt qua một đầu danh sách mà bạn xem như vô cực.

Làm thế nào để trả về trung vị mà không dùng số thực?

Cộng hai giá trị ở giữa dưới dạng số nguyên. Chia tổng chẵn cho 2. Với tổng lẻ, viết một nửa giá trị tuyệt đối của tổng rồi thêm .5, thêm dấu trừ nếu tổng âm: -1 trở thành "-0.5".

def findMedianSortedArrays(nums1, nums2):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

nums1 = [1, 4]
nums2 = [2, 7, 9]

Đầu ra mong đợi

"4"