在两个都有序的数组中找整体第K小的数。
1.A和B长度不等的时候，需要把A和B的长度变成相等。
A是短数组，B是长数组。
第k小的数，k从1开始。
k<=短，都取前k个数，变成等长。
短<k<=长，长取中，长扣1。
长<k<=和,两个数组都取后 变成等长，两个数组都需要扣掉1个元素，小被干，都需要扣掉左边。
2.A和B长度相等的时候。分长度是偶数和长度是奇数两种情况。都是求中位数。
2.1.A和B长度相等，并且长度是偶数。
A=[A1,A2,A3,A4]
B=[B1,B2,B3,B4]
当A2==B2时，取A2。
当A2>B2时，B1、B2、A3、A4去掉。递归。
2.2.A和B长度相等，并且长度是奇数。
A=[A1,A2,A3,A4,A5]
B=[B1,B2,B3,B4,B5]
当A3==B3时，取A3。
当A3>B3时，B1、B2、A3、A4、A5去掉。当A2<=B3时，取B3；否则去掉B3，递归。
时间复杂度是O(log(min(M,N)))。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
arr1 := []int{1, 3}
arr2 := []int{2}
ret := findMedianSortedArrays(arr1, arr2)
fmt.Println(ret)
}
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
size := len(nums1) + len(nums2)
even := (size & 1) == 0
if len(nums1) != 0 && len(nums2) != 0 {
if even {
return float64(findKthNum(nums1, nums2, size/2)+findKthNum(nums1, nums2, size/2+1)) / 2.0
} else {
return float64(findKthNum(nums1, nums2, size/2+1))
}
} else if len(nums1) != 0 {
if even {
return float64((nums1[(size-1)/2] + nums1[size/2]) / 2)
} else {
return float64(nums1[size/2])
}
} else if len(nums2) != 0 {
if even {
return float64((nums2[(size-1)/2] + nums2[size/2]) / 2)
} else {
return float64(nums2[size/2])
}
} else {
return 0
}
}
// 进阶问题 : 在两个都有序的数组中，找整体第K小的数
// 可以做到O(log(Min(M,N)))
func findKthNum(arr1 []int, arr2 []int, kth int) int {
longs := twoSelectOne(len(arr1) >= len(arr2), arr1, arr2)
shorts := twoSelectOne(len(arr1) < len(arr2), arr1, arr2)
l := len(longs)
s := len(shorts)
if kth <= s { // 1)
return getUpMedian(shorts, 0, kth-1, longs, 0, kth-1)
}
if kth > l { // 3)
if shorts[kth-l-1] >= longs[l-1] {
return shorts[kth-l-1]
}
if longs[kth-s-1] >= shorts[s-1] {
return longs[kth-s-1]
}
return getUpMedian(shorts, kth-l, s-1, longs, kth-s, l-1)
}
// 2) s < k <= l
if longs[kth-s-1] >= shorts[s-1] {
return longs[kth-s-1]
}
return getUpMedian(shorts, 0, s-1, longs, kth-s, kth-1)
}
// A[s1...e1]
// B[s2...e2]
// 一定等长！
// 返回整体的，上中位数！8（4） 10（5） 12（6）
func getUpMedian(A []int, s1 int, e1 int, B []int, s2 int, e2 int) int {
mid1 := 0
mid2 := 0
for s1 < e1 {
// mid1 = s1 + (e1 - s1) >> 1
mid1 = (s1 + e1) / 2
mid2 = (s2 + e2) / 2
if A[mid1] == B[mid2] {
return A[mid1]
}
// 两个中点一定不等！
if ((e1 - s1 + 1) & 1) == 1 { // 奇数长度
if A[mid1] > B[mid2] {
if B[mid2] >= A[mid1-1] {
return B[mid2]
}
e1 = mid1 - 1
s2 = mid2 + 1
} else { // A[mid1] < B[mid2]
if A[mid1] >= B[mid2-1] {
return A[mid1]
}
e2 = mid2 - 1
s1 = mid1 + 1
}
} else { // 偶数长度
if A[mid1] > B[mid2] {
e1 = mid1
s2 = mid2 + 1
} else {
e2 = mid2
s1 = mid1 + 1
}
}
}
return getMin(A[s1], B[s2])
}
func getMin(a int, b int) int {
if a < b {
return a
} else {
return b
}
}
func twoSelectOne(c bool, a []int, b []int) []int {
if c {
return a
} else {
return b
}
}执行结果如下：
