There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
<pre><code>`nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
如果不考虑时间复杂度，最简单就是将两个数组合并，然后寻找中位数:
func findMedianSortedArrays(_ nums1: [Int], _ nums2: [Int]) -> Double {
var index1:Int = 0
var index2:Int = 0
var preNum = 0
var currentNum = 0
var count:Int = 0
let count1 = nums1.count
let count2 = nums2.count
let midIndex = (count1 + count2) / 2
while index1 < count1 && index2 < count2 {
if count - 1 == midIndex {
break
}
preNum = currentNum
if nums1[index1] < nums2[index2] {
currentNum = nums1[index1]
index1 += 1
} else {
currentNum = nums2[index2]
index2 += 1
}
count += 1
}
while index1 < count1 {
if count - 1 == midIndex {
break
}
preNum = currentNum
currentNum = nums1[index1]
index1 += 1
count += 1
}
while index2 < count2 {
if count - 1 == midIndex {
break
}
preNum = currentNum
currentNum = nums2[index2]
index2 += 1
count += 1
}
var result:Double = 0
if (count1 + count2) % 2 == 0 {
result = Double(preNum + currentNum) / 2.0
} else {
result = Double(currentNum)
}
return result
}
按照题目要求的复杂度，可以通过二分法递归实现，找两个已排序数组的中位数，其实就是将两个有序数组有序合并后找第K小的数。而找第K小的数，可以将K平分到两个数组中，然后利用一个重要的结论：如果A[k/2-1]<B[k/2-1]，那么A[0]~A[k/2-1]一定在第k小的数的序列当中.
func findMedianSortedArrays3(_ nums1: [Int], _ nums2: [Int]) -> Double {
let count = nums1.count + nums2.count
if count % 2 == 1 {
return findKth(num1: num1, m: num1.count, num2: num2, n: num2.count, k: count / 2 + 1)
} else {
let mid1:Double = findKth(num1: num1, m: num1.count, num2: num2, n: num2.count, k: count / 2 + 1)
let mid2:Double = findKth(num1: num1, m: num1.count, num2: num2, n: num2.count, k: count / 2)
return (mid1 + mid2) / 2
}
}
func findKth(num1:[Int], m:Int, num2:[Int], n:Int, k:Int) -> Double {
// 假定第一个数组为较小数组
if m > n {
return findKth(num1: num2, m: n, num2: num1, n: m, k: k)
}
if m == 0 {
return Double(num2[k - 1])
}
if k == 1 {
return Double(min(num1[0], num2[0]))
}
let lenA = min(k / 2, m)
let lenB = k - lenA
if num1[lenA - 1] < num2[lenB - 1] {
let temp:[Int] = num1
return findKth(num1: Array(temp.suffix(from: lenA)), m: m - lenA, num2: num2, n: n, k: k - lenA)
} else if num1[lenA - 1] > num2[lenB - 1] {
let temp:[Int] = num2
return findKth(num1: num1, m: m, num2:Array(temp.suffix(from: lenB)) , n: n - lenB, k: k - lenB)
} else {
return Double(num2[lenA - 1])
}
}
- 保持num1是短的那一个数组，num2是长的
- 平分k, 一半在num1，一半在num2 (如果num1的长度不足K/2,那就pa就指到最后一个）
- 如果lenA的值 < lenB的值，那证明第K个数肯定不会出现在pa之前，递归，把num1数组pa之前的数据删除.同理递归砍B数组.
- 递归到 m == 0(num1为空)返回 B[k - 1], 或者k == 1（找第一个数）就返回min(num1第一个数num2第一个数）
