此教程使用C++版本編寫代碼,如需其他版本,請自行修改,并在力扣網(wǎng)站中測試!
題目描述
給定兩個大小分別為 m 和 n 的正序(從小到大)數(shù)組 nums1 和 nums2。請你找出并返回這兩個正序數(shù)組的 中位數(shù) 。
算法的時間復(fù)雜度應(yīng)該為 O(log (m+n)) 。
示例1:
輸入:nums1 = [1,3], nums2 = [2]
輸出:2.00000
解釋:合并數(shù)組 = [1,2,3] ,中位數(shù) 2
示例2:
輸入:nums1 = [1,2], nums2 = [3,4]
輸出:2.50000
解釋:合并數(shù)組 = [1,2,3,4] ,中位數(shù) (2 + 3) / 2 = 2.5
提示:
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106
C++題目源碼:
解決方案一:
//中位數(shù)的理解:
//有序序列
//總數(shù)是奇數(shù)
//1 2 3 4 5 5/2 =2
//總數(shù)是偶數(shù)
//1 2 3 4 5 6 6/2=3 (3+4)/2.0=3.5
//合并兩個有序序列
//查找中位數(shù)即可
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
{
//合并得到一個有序序列
vector<int> result;
for(auto& v:nums1)
{
result.push_back(v);
}
for(auto& v:nums2)
{
result.push_back(v);
}
sort(result.begin(),result.end());
//分為奇數(shù)和偶數(shù)的情況輸出中位數(shù)即可
int length=result.size();
if((length+1)%2==0) //奇數(shù)個長度
{
return result[length/2];
}
else
{
int pos=length/2;
return (result[pos-1]+result[pos])/2.0;
}
}
};
解決方案二:
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
{
vector<int> result(nums1.size()+nums2.size());
if(nums1.size()==0)
{
copy(nums2.begin(),nums2.end(),result.begin());
}
else if(nums2.size()==0)
{
copy(nums1.begin(),nums1.end(),result.begin());
}
else
{
merge(nums1.begin(),nums1.end(),nums2.begin(),nums2.end(),result.begin());
}
int pos=result.size()/2;
return pos!=0&&result.size()%2==0?(result[pos-1]+result[pos])/2.0:result[pos];
}
};
聲明:本文內(nèi)容及配圖由入駐作者撰寫或者入駐合作網(wǎng)站授權(quán)轉(zhuǎn)載。文章觀點僅代表作者本人,不代表電子發(fā)燒友網(wǎng)立場。文章及其配圖僅供工程師學(xué)習(xí)之用,如有內(nèi)容侵權(quán)或者其他違規(guī)問題,請聯(lián)系本站處理。
舉報投訴
-
C++
+關(guān)注
關(guān)注
22文章
2114瀏覽量
73788 -
代碼
+關(guān)注
關(guān)注
30文章
4821瀏覽量
68893 -
編寫
+關(guān)注
關(guān)注
0文章
29瀏覽量
8486
發(fā)布評論請先 登錄
相關(guān)推薦
怎樣將兩個數(shù)組比較
我用圖像得到兩個三維數(shù)組,把這兩個數(shù)組進(jìn)行運算,得出值相同的部分,怎樣用labview實現(xiàn)。由于得到的數(shù)組都很大,可以先簡化一下的
發(fā)表于 04-18 10:19
兩個一維數(shù)組中相同元素的個數(shù)
各位大神,請教個問題,兩個一維數(shù)組,每個數(shù)組中約有6萬個元素,元素都是唯一的,統(tǒng)計兩個數(shù)組中相同元素個數(shù),使用如下程序,速度較慢,有沒有其他
發(fā)表于 04-07 17:27
兩個一維數(shù)組,找出短的缺失的元素
一長一短兩個一維數(shù)組,短的比長的缺失幾個元素,怎么找到缺失的元素并用數(shù)組顯示出來,比如【1,2,3,4,5】和【1,2,5】得出【3,4】,求大神解答,就如圖所示
發(fā)表于 03-10 11:18
labview比較兩個元素數(shù)值大小,并進(jìn)行統(tǒng)計
labview 中怎么比較兩個二位數(shù)組元素數(shù)值的大小,兩個數(shù)組的數(shù)據(jù)長度是一樣的,然后統(tǒng)計兩個數(shù)組中元素不同的元素數(shù)量除數(shù)組的長度大小,輸出
發(fā)表于 05-12 18:13
兩個一維數(shù)組無法生成XY圖
`兩個一位數(shù)組,一直沒辦法生成XY圖始終報錯:由于數(shù)據(jù)類型(數(shù)值、字符串、數(shù)組和簇等)不匹配,將無法連線這些對象。顯示即時幫助窗口可查看所需的數(shù)據(jù)類型。數(shù)據(jù)源的類型是簇 2 元素。數(shù)據(jù)接收端的類型是1D
發(fā)表于 03-10 22:39
各位大佬 有兩個兩組 一個X軸數(shù)組 一個Y軸數(shù)組 兩個數(shù)組合成一個波形 怎么求這個波形的對稱度?
各位大佬 有兩個兩組 一個X軸數(shù)組 一個Y軸數(shù)組 兩個數(shù)組
發(fā)表于 09-26 10:40
有關(guān)中位數(shù)計算是什么
?中位數(shù)是數(shù)理統(tǒng)計中一個重要的指標(biāo),它可以自動忽略數(shù)據(jù)極差帶來的影響,
??能夠很好的評估數(shù)據(jù),在數(shù)理統(tǒng)計中很常用。本文主要介紹在Python中和Mysql
中如何來求中位數(shù),重點讓大家掌握SQL計算
C 語言數(shù)組的基本結(jié)構(gòu)
的元素 求數(shù)組中元素的最短距離 求兩個有序數(shù)組的共同元素 求三個數(shù)組的共同元素 找出數(shù)組中唯一的重復(fù)元素 找出出現(xiàn)奇數(shù)次的元素 求
評論