題目描述
給定兩個(gè)大小為 m 和 n 的有序數(shù)組 nums1 和 nums2。
請(qǐng)你找出這兩個(gè)有序數(shù)組的中位數(shù)，并且要求算法的時(shí)間復(fù)雜度為 O(log(m + n))。
你可以假設(shè) nums1 和 nums2 不會(huì)同時(shí)為空。
示例
示例 1:
nums1 = [1, 3]
nums2 = [2]
則中位數(shù)是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
則中位數(shù)是 (2 + 3)/2 = 2.5
解題思路1
暴力解法很容易想到，把兩個(gè)有序數(shù)組合并(O(m+n)), 再取出中位數(shù)(O(1)),時(shí)間復(fù)雜度上不符合要求。
不額外開(kāi)辟空間存儲(chǔ)合并之后的數(shù)組，只用兩個(gè)指針記錄也是一樣的，這樣可以節(jié)省存儲(chǔ)空間和時(shí)間，但是不會(huì)有
時(shí)間復(fù)雜度的提升，本質(zhì)上都是暴力方法。
C++
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int i = 0;
int j = 0;
int size1 = nums1.size();
int size2 = nums2.size();
vector<int> merge;
while (i < size1 && j < size2)
{
if (nums1[i] <= nums2[j])
{
merge.push_back(nums1[i]);
i++;
}
else
{
merge.push_back(nums2[j]);
j++;
}
}
while (i < size1)
{
merge.push_back(nums1[i]);
i++;
}
while (j < size2)
{
merge.push_back(nums2[j]);
j++;
}
int size3 = merge.size();
if (size3 % 2 == 0)
{
int pos2 = size3 / 2;
int pos1 = pos2 - 1;
float ans = (merge[pos1] + merge[pos2]) / 2.0;
return ans;
}
else
{
float ans = (float)merge[size3 / 2];
return ans;
}
return -1;
}
};
python
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
i = 0
j = 0
merge = []
while (i < len(nums1) and j < len(nums2)):
if nums1[i] <= nums2[j]:
merge.append(nums1[i])
i = i + 1
else:
merge.append(nums2[j])
j = j + 1
while i < len(nums1):
merge.append(nums1[i])
i = i + 1
while j < len(nums2):
merge.append(nums2[j])
j = j + 1
if (len(merge) % 2 == 0):
pos2 = len(merge) // 2
pos1 = pos2 - 1
ans = (merge[pos1] + merge[pos2]) / 2.0
return ans
else:
ans = float( merge[len(merge) // 2] )
return ans
