leetcode最小字符串长度（LeetCode求两个有序数组的中位数）

首先来看一下题目：

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})) }