題目:
給定兩個大小分别為 m 和 n 的正序(從小到大)數組 nums1 和 nums2。請你找出并傳回這兩個正序數組的 中位數 。
算法的時間複雜度應該為 O(log (m+n)) 。
示例 1:
輸入:nums1 = [1,3], nums2 = [2]
輸出:2.00000
解釋:合并數組 = [1,2,3] ,中位數 2
示例 2:
輸入:nums1 = [1,2], nums2 = [3,4]
輸出:2.50000
解釋:合并數組 = [1,2,3,4] ,中位數 (2 + 3) / 2 = 2.5
思路:
根據替題目提幹,以及示例的提示可知,題目的目的是将兩個有序數組合并為一個有序數組後,找到新新數組的中位數。中位數在數組中的index 取決于數組的長度的奇偶性。
int size = 新數組.size();
size == 偶數: 中位數的index:
int n = size/2;
index = n + n-1;
size == 奇數:中位數的index:
index = size/2
//實作一:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int size1 = nums1.size();
int size2 = nums2.size();
std::vector<int> vResult;
int i = 0, j = 0;
for(int count = 0 ;count < size1+size2; count++)
{
if(i< size1 && j < size2)
{
if(nums1[i] < nums2[j])
{
vResult.push_back(nums1[i]);
i++;
}
else if(nums1[i] > nums2[j])
{
vResult.push_back(nums2[j]);
j++;
}
else
{
vResult.push_back(nums1[i]);
vResult.push_back(nums2[j]);
j++;
i++;
}
}
else if(j < size2 && i == size1)
{
for(;j<size2;j++)
{
vResult.push_back(nums2[j]);
}
}
else if(i < size1 && j == size2)
{
for(;i<size1;i++)
{
vResult.push_back(nums1[i]);
}
}
}
int sizeResult = vResult.size();
if(sizeResult % 2 != 0)
{
return static_cast<float>(vResult[(vResult.size()-1)/2]);
}
else
{
int n = sizeResult/2;
return static_cast<float>((vResult[n] + vResult[n-1])/2.0);
}
}
//實作二: 調用vector 的庫函數 sort來實作vector中資料排序
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
for(unsigned i = 0;i < nums2.size();i++)
{
nums1.push_back(nums2[i]);
}
sort(nums1.begin(),nums1.end());
int sizeResult = nums1.size();
float out;
if(sizeResult % 2 != 0)
{
out = static_cast<float>(nums1[(sizeResult-1)/2]);
}
else
{
int n = sizeResult/2;
out = static_cast<float>((nums1[n] + nums1[n-1])/2.0);
}
return out;
}