首先來看一下題目：

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m n)).

Example 1:

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

Output: 2.00000

Explanation: merged array = [1,2,3] and median is 2.

Example 2:

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

Output: 2.50000

Explanation: merged array = [1,2,3,4] and median is (2 3) / 2 = 2.5.

Example 3:

Input: nums1 = [0,0], nums2 = [0,0]

Output: 0.00000

Example 4:

Input: nums1 = [], nums2 = [1]

Output: 1.00000

Example 5:

Input: nums1 = [2], nums2 = []

Output: 2.00000

Constraints:

nums1.length == m

nums2.length == n

0 <= m <= 1000

0 <= n <= 1000

1 <= m n <= 2000

-10^6 <= nums1[i], nums2[i] <= 10^6

題目的意思是：有兩個有序數組nums1、nums2長度分别是m、n，求他們的中位數。時間複雜度要求為O(log (m n))。

方法一：

一個顯而易見的方法總是存在的，不管它有多笨。暴力一點，直接merge以後求中位數。

package main import "fmt" func findMedianSortedArrays(nums1 []int, nums2 []int) float64 { m := merge(nums1, nums2) if (len(nums1) len(nums2))%2 != 0 { return float64(m[(len(nums1) len(nums2) 1)/2-1]) } return float64((m[(len(nums1) len(nums2))/2-1] m[(len(nums1) len(nums2))/2])) / 2 } func merge(a, b []int) []int { result := []int{} i, j := 0, 0 for i < len(a) && j < len(b) { if a[i] <= b[j] { result = append(result, a[i]) i } else { result = append(result, b[j]) j } } for ; i < len(a); i { result = append(result, a[i]) } for ; j < len(b); j { result = append(result, b[j]) } return result } func main() { fmt.Println(findMedianSortedArrays([]int{}, []int{1, 2})) }

但是時間複雜度為O(m n)，不滿足要求。

方法二：

仍然是merge的思想，但是我們不一一merge，而是二分merge，這樣時間複雜度就會降到log級别。

如上圖所示，整體中位數長度不會超過長度len(nums1 nums2)/2 1，所以如果在nums1中存在一個位置i，那麼nums2會存在一個位置j為len(nums1 nums2)/2 1-(i 1)-1。

我們知道nums1是有序的，所以一定有nums1[i]<=nums1[i 1]且nums2[j]<=nums2[j 1]。如果再滿足nums1[i]<=nums2[j 1]且nums2[j]<=nums1[i 1]的話，則可以确定整體的中位數必然存在于nums1[0:i 1]和nums2[0:j 1]中，這樣就求出了整體的中位數。

圖中還可見，我們把nums1放在上面，這樣的話時間複雜度就是O(min(log m, log n))，比題目中要求的更快。下面看一下代碼：

package main import "fmt" func findMedianSortedArrays(nums1 []int, nums2 []int) float64 { left, right := nums1, nums2 if len(nums1) > len(nums2) { left, right = nums2, nums1 } i := findIndexOfLeft(left, right, 0, len(left)-1) sumLen := len(left) len(right) if sumLen%2 == 0 { if i == -1 { return float64(right[sumLen/2-1] right[sumLen/2]) / 2 } x, y := 0, 0 j := sumLen/2 1 - (i 1) - 1 if left[i] > right[j] { y = left[i] if i-1 >= 0 { if left[i-1] > right[j] { x = left[i-1] } else { x = right[j] } } else { x = right[j] } } else { y = right[j] if j-1 >= 0 { if right[j-1] > left[i] { x = right[j-1] } else { x = left[i] } } else { x = left[i] } } return float64(x y) / 2 } else { if i == -1 { return float64(right[sumLen/2]) } j := sumLen/2 1 - (i 1) - 1 if left[i] > right[j] { return float64(left[i]) } return float64(right[j]) } } func findIndexOfLeft(left, right []int, i, j int) int { if i <= j { leftMid := i (j-i)/2 rightMid := (len(left) len(right))/2 1 - (i (j-i)/2 1) - 1 if leftMid 1 >= len(left) { if rightMid 1 >= len(right) || left[leftMid] <= right[rightMid 1] { return leftMid } j = leftMid - 1 return findIndexOfLeft(left, right, i, j) } if rightMid 1 >= len(right) { if right[rightMid] <= left[leftMid 1] { return leftMid } i = leftMid 1 return findIndexOfLeft(left, right, i, j) } if left[leftMid] <= right[rightMid 1] && right[rightMid] <= left[leftMid 1] { return leftMid } if left[leftMid] > right[rightMid 1] { j = leftMid - 1 return findIndexOfLeft(left, right, i, j) } if right[rightMid] > left[leftMid 1] { i = leftMid 1 return findIndexOfLeft(left, right, i, j) } } return -1 } func main() { fmt.Println(findMedianSortedArrays([]int{4, 6, 7}, []int{1, 2, 3})) }

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!