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
如果不考慮時(shí)間復(fù)雜度桑谍，最簡(jiǎn)單就是將兩個(gè)數(shù)組合并赎线，然后尋找中位數(shù):
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
}
按照題目要求的復(fù)雜度巨税，可以通過二分法遞歸實(shí)現(xiàn)派撕，找兩個(gè)已排序數(shù)組的中位數(shù)，其實(shí)就是將兩個(gè)有序數(shù)組有序合并后找第K小的數(shù)质欲。而找第K小的數(shù)免绿，可以將K平分到兩個(gè)數(shù)組中可帽，然后利用一個(gè)重要的結(jié)論：如果A[k/2-1]<B[k/2-1]，那么A[0]~A[k/2-1]一定在第k小的數(shù)的序列當(dāng)中.
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 {
// 假定第一個(gè)數(shù)組為較小數(shù)組
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是短的那一個(gè)數(shù)組鳄袍，num2是長(zhǎng)的
- 平分k, 一半在num1绢要，一半在num2 (如果num1的長(zhǎng)度不足K/2,那就pa就指到最后一個(gè)）
- 如果lenA的值 < lenB的值，那證明第K個(gè)數(shù)肯定不會(huì)出現(xiàn)在pa之前拗小，遞歸重罪，把num1數(shù)組pa之前的數(shù)據(jù)刪除.同理遞歸砍B數(shù)組.
- 遞歸到 m == 0(num1為空)返回 B[k - 1], 或者k == 1（找第一個(gè)數(shù)）就返回min(num1第一個(gè)數(shù)num2第一個(gè)數(shù)）
