4. Median of Two Sorted Arrays

Đề bài

Cho hai mảng đã sắp xếp nums1 và nums2, có độ dài lần lượt là $m$ và $n$.

Hãy tìm trung vị (median) của hai mảng này. Yêu cầu độ phức tạp thời gian (time complexity) tổng thể phải là $O(\log(m+n))$.

Bạn có thể giả định nums1 và nums2 không thể đồng thời rỗng.

Ví dụ 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Ví dụ 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

Tóm tắt đề

Cho hai mảng đã sắp xếp nums1 và nums2 có kích thước lần lượt là $m$ và $n$.

Hãy tìm trung vị của hai mảng sau khi “gộp” lại theo thứ tự tăng dần, với yêu cầu độ phức tạp thời gian là $O(\log(m+n))$.

Bạn có thể giả định nums1 và nums2 không bao giờ đồng thời rỗng.

Ý tưởng

• Ta có 2 mảng đã sắp xếp, cần tìm trung vị của mảng sau khi gộp lại, và bắt buộc chạy trong $O(\log(m+n))$.
• Cách dễ nghĩ nhất là gộp 2 mảng rồi lấy trung vị, nhưng gộp như vậy tốn O(m+n) nên không đạt yêu cầu. Thấy yêu cầu dạng log thì hướng đúng thường là tìm kiếm nhị phân (binary search).
• Vì ta biết tổng số phần tử $m+n$, nên “vị trí ở giữa” cũng được xác định. Ta sẽ nhị phân trên mảng ngắn hơn để tìm vị trí cắt (partition) sao cho hai nửa trái/phải ghép lại vẫn đúng thứ tự.
• Gọi vị trí cắt của nums1 là midA, khi đó vị trí cắt của nums2 sẽ là midB sao cho tổng số phần tử ở nửa trái bằng $k = \lfloor (m+n+1)/2 \rfloor$. Điều kiện để phép cắt hợp lệ (tất cả phần tử bên trái ≤ tất cả phần tử bên phải) là: nums1[midA-1] ≤ nums2[midB] && nums2[midB-1] ≤ nums1[midA] Nếu chưa thỏa, ta điều chỉnh midA:
  • Nếu nums1[midA] < nums2[midB-1] thì phía trái của nums1 đang “thiếu” (cắt quá ít) ⇒ dịch midA sang phải.
  • Nếu nums1[midA-1] > nums2[midB] thì phía trái của nums1 đang “thừa” (cắt quá nhiều) ⇒ dịch midA sang trái. Lặp lại cho tới khi tìm được partition hợp lệ.
• Khi đã có midA, midB:

  • Nếu tổng độ dài là lẻ, trung vị là max(nums1[midA-1], nums2[midB-1]).

  • Nếu tổng độ dài là chẵn, hai số ở giữa là max(nums1[midA-1], nums2[midB-1]) và min(nums1[midA], nums2[midB]), nên trung vị là: (max(nums1[midA-1], nums2[midB-1]) + min(nums1[midA], nums2[midB])) / 2 Hình minh họa xem bên dưới:

    

Code

package leetcode

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	// Giả sử nums1 là mảng ngắn hơn (để nhị phân trên mảng nhỏ)
	if len(nums1) > len(nums2) {
		return findMedianSortedArrays(nums2, nums1)
	}
	low, high, k, nums1Mid, nums2Mid := 0, len(nums1), (len(nums1)+len(nums2)+1)>>1, 0, 0
	for low <= high {
		// nums1:  ……………… nums1[nums1Mid-1] | nums1[nums1Mid] ……………………
		// nums2:  ……………… nums2[nums2Mid-1] | nums2[nums2Mid] ……………………
		nums1Mid = low + (high-low)>>1 // Bên phải là mid, bên trái là mid-1
		nums2Mid = k - nums1Mid
		if nums1Mid > 0 && nums1[nums1Mid-1] > nums2[nums2Mid] { // Cắt quá nhiều ở nums1 → dịch sang trái
			high = nums1Mid - 1
		} else if nums1Mid != len(nums1) && nums1[nums1Mid] < nums2[nums2Mid-1] { // Cắt quá ít ở nums1 → dịch sang phải
			low = nums1Mid + 1
		} else {
			// Đã tìm được vị trí cắt hợp lệ; chuẩn bị xuất kết quả (trường hợp tổng lẻ/tổng chẵn)
			break
		}
	}
	midLeft, midRight := 0, 0
	if nums1Mid == 0 {
		midLeft = nums2[nums2Mid-1]
	} else if nums2Mid == 0 {
		midLeft = nums1[nums1Mid-1]
	} else {
		midLeft = max(nums1[nums1Mid-1], nums2[nums2Mid-1])
	}
	if (len(nums1)+len(nums2))&1 == 1 {
		return float64(midLeft)
	}
	if nums1Mid == len(nums1) {
		midRight = nums2[nums2Mid]
	} else if nums2Mid == len(nums2) {
		midRight = nums1[nums1Mid]
	} else {
		midRight = min(nums1[nums1Mid], nums2[nums2Mid])
	}
	return float64(midLeft+midRight) / 2
}

---