本期給大家?guī)淼氖鞘恰?strong>LeetCode 熱題 HOT 100》第四題——尋找兩個正序數(shù)組的中位數(shù)的題目講解?。。。ǎ?/strong>
本文目錄
??題意分析
??解題思路:
1、直接法? (?)
2、歸并思想?(?)
①《LeetCode》第88題——合并兩個有序數(shù)組
3、二分查找(??)
整體思想:
題目如下 :??
給定兩個大小分別為 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
??題意分析
首先,我們需要注意的一點就是關(guān)于本題時間復(fù)雜度的要求,本題要求的時間復(fù)雜度為? O(log (m+n)) ,這里一定要特別注意!!
其次,我們來對給出的示例給出解釋說明,分析題意:
- 首先對于示例一,題目給出了兩個數(shù)組——nums1和nums2,兩個數(shù)組的的合并之后且排好序之后為 【1 2 3】,又因為是 double型 輸出,此時它的中位數(shù)就是 【2.00000】;
- 其次對于示例二,題目給出了兩個數(shù)組,數(shù)組中的元素分別為【1 2】和【3 4】,此時經(jīng)過排序,我們得到【1 2 3 4】這樣的數(shù)組,此時數(shù)組的長度為偶數(shù),因此中位數(shù)的計算就是【(2 + 3) / 2 = 2.5】
??解題思路:
1、直接法? (?)
首先,大家拿道題,第一種想到的可能就是直接對這兩個數(shù)組進行合并在進行排序處理,排完序之后緊接著根據(jù)數(shù)據(jù)長度的奇偶性,我們來判斷中位數(shù)的到底是n/2還是n/2+1:
代碼如下:
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
vector<int>arr;
for(auto& e :nums1) {arr.push_back(e);}
for(auto& e :nums2) {arr.push_back(e);}
sort(arr.begin(),arr.end());
int m=arr.size();
if( m % 2 == 0){
return (double)(arr[m/2]+arr[m/2-1]) /2.0;
} else{
return arr[m/2];
}
}
};
???? 這種做法可以通過但是卻不符合提本題的要求,因為它的時間復(fù)雜度就為了?O((m+n)log (m+n)),這樣做時間復(fù)雜度就取決于排序的代價。因此,這種方法我就此忽略。
2、歸并思想?(?)
其實我們在稍加思考,就可以想到一種優(yōu)化方法。
???? 我們可以聯(lián)想到歸并排序,這個我想大概應(yīng)該都學過的。我們不用在進行先合并在sorted,我們可以直接把這兩個歸并為一個已經(jīng)排序好的數(shù)組。此時這就是雙指針的算法,時間復(fù)雜度此時為O(m+n)。
這個還可以進行優(yōu)化,我們不需要對全部進行歸并操作,因為我們只關(guān)心中位數(shù),因此我們可以計算中位數(shù)的下標,假設(shè)此時中位數(shù)的下表為?k,時間復(fù)雜度就為O(k),k的取值取決于數(shù)組的長度還是,介于(m+n)/2和?(m+n)/2+1。但是此時依然也不能滿足我們題意的 log 級別的時間復(fù)雜度的要求.
?
①《LeetCode》第88題——合并兩個有序數(shù)組
注意:
- 如果大家對這個排序還不熟悉的小伙伴,我在這里就連帶還給出了以下題目的講解,幫助大家認識 歸并排序 思想 :
- 《LeetCode》第88題——合并兩個有序數(shù)組??
題目如下:
給你兩個按 非遞減順序 排列的整數(shù)數(shù)組?nums1 和 nums2,另有兩個整數(shù) m 和 n ,分別表示 nums1 和 nums2 中的元素數(shù)目。
請你 合并 nums2 到 nums1 中,使合并后的數(shù)組同樣按 非遞減順序 排列。
注意:
- 最終,合并后數(shù)組不應(yīng)由函數(shù)返回,而是存儲在數(shù)組 nums1 中。為了應(yīng)對這種情況,nums1 的初始長度為 m + n,其中前 m 個元素表示應(yīng)合并的元素,后 n 個元素為 0 ,應(yīng)忽略。nums2 的長度為 n 。
示例 1:
輸入:nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
輸出:[1,2,2,3,5,6]
解釋:需要合并 [1,2,3] 和 [2,5,6] 。
合并結(jié)果是 [1,2,2,3,5,6] ,其中斜體加粗標注的為 nums1 中的元素。
示例 2:
輸入:nums1 = [1], m = 1, nums2 = [], n = 0
輸出:[1]
解釋:需要合并 [1] 和 [] 。
合并結(jié)果是 [1] 。
示例 3:
輸入:nums1 = [0], m = 0, nums2 = [1], n = 1
輸出:[1]
解釋:需要合并的數(shù)組是 [] 和 [1] 。
合并結(jié)果是 [1] 。
注意,因為 m = 0 ,所以 nums1 中沒有元素。nums1 中僅存的 0 僅僅是為了確保合并結(jié)果可以順利存放到 nums1 中。
??題意分析:
- 首先,根據(jù)題意,我們可以知道給出了的數(shù)據(jù)都是已經(jīng)排好序的了,因此,這就減少了我們的一步操作;
- 緊接著我們可以發(fā)現(xiàn)最終是由nums1返回,因此它的空間都足夠大
??解題思路:
1、直接法
- 最容易想到的辦法無疑是把數(shù)組?nums2? 的數(shù)據(jù)元素全部放入到數(shù)組?nums1 的尾部,因此題意告訴我們 nums1 的空間大小為【m+n】,然后直接對整個數(shù)組進行排序即可。
代碼如下:
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
//此時我們選nums1作為 填充數(shù)組,把nums2中元素全部插入到nums1中
for(int i=0; i<n; ++i)
{
nums1[m+i]=nums2[i];
}
//此時,全部的元素都在nums1數(shù)組中了,最后排序輸出即可
sort(nums1.begin(),nums1.end());
}
};
性能分析:
- 時間復(fù)雜度:跟我們上述暴力解《尋找兩個正序數(shù)組的中位數(shù)》一樣,此時 時間復(fù)雜度為O((m+n)log(m+n))
- 空間復(fù)雜度:因為初始時nums1 的空間長度大小已經(jīng)為 (m+n)了。因此無需在開辟額外的空間對其進行存放操作,因此 空間復(fù)雜度為O(1)
2、歸并排序思想
- 如果我們仔細觀察這到題很明顯就是需要利用 二路歸并排序?的思想來做。先確定排序后數(shù)組的長度,緊接著比較兩數(shù)組最后的元素的大小,大的放入新數(shù)組的最后一位。(因為本題 nums1 數(shù)組的長度是 (m+n),所以我們直接覆蓋到 nums1 數(shù)組之后即可)
圖解:
- 開始時如下圖所示:
- ?第一步,比較 3和6 的大小,此時 6比3 大,因此,把6插入到末尾,同時 l2和tail 兩個指針同時往前移動一個位置
- ?第二步:此時在比較 3和5 的大小,發(fā)現(xiàn)5比3大,因此同上述操作一樣,把 5 插入到 tail指向的位置,同時兩個指針在往前移動一位
?
- 第三步:此時比較 3和2 的大小,發(fā)現(xiàn)此時 3比2 大,因此,把3插入到 tail指向的位置,同時? tail和 l1 在往前移動一位
- ?第四步:緊接著再次比較 2和2 的大小,發(fā)現(xiàn)此時一樣大,隨便取 l1和l2 位置對應(yīng)的元素插入到 tail處即可,我們這里是把 l2位置處的 插入到 tail 處。同時移動 l2和tail?
?
- 第五步:此時 nums2的數(shù)據(jù) 已經(jīng)處理完畢了,nums1 中還有數(shù)據(jù),只需把 nums1 剩余的元素 放入 tail 所指的位置即可,最后完成排序。
代碼如下:
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int l1 = m - 1;
int l2 = n - 1;
int tail = m + n - 1;
while (l1 >= 0 && l2 >= 0)
{
if (nums1[l1] > nums2[l2])
{
nums1[tail--] = nums1[l1--];
}
else
{
nums1[tail--] = nums2[l2--];
}
}
while (l1 >= 0)
{
nums1[tail--] = nums1[l1--];
}
while (l2 >= 0)
{
nums1[tail--] = nums2[l2--];
}
}
};
性能分析:
- 時間復(fù)雜度:指針移動單調(diào)遞減,最多移動?m+n 次,因此 時間復(fù)雜度為?O(m+n)。
- 空間復(fù)雜度:直接對數(shù)組?nums1 原地修改,不需要額外空間,因此 空間復(fù)雜度為O(1)。
溫馨小提示:
我們除了從后往前操作之外,還有從前往后操作。這個任務(wù)就交給大家了,原理跟上面講到的一樣的?。?!
3、二分查找(??)
最后,其實我們可以想到,要想實現(xiàn) log 級別的時間復(fù)雜度,最容易想到的就是采用二分查找的思想。
但是二分查找,我們之前學過的都是對一個數(shù)組進行二分查找,本題我們這里有兩個數(shù)組,因此此題的難度我們可以看到標的是 困難。但是也不要害怕,接下來我?guī)Т蠹曳治鲆徊?br> ?
整體思想:
- 更有效的方法是使用二叉搜索,我們可以在兩個數(shù)組中找到分區(qū)點,使得分區(qū)點左側(cè)的元素小于右側(cè)的元素。然后,可以通過取左分區(qū)的最大值和右分區(qū)的最小值來找到中位數(shù)?。?!
圖解:
?
- ?分區(qū)點不滿足的示例:
- 極端情況1:
- ?極端情況2:
?
?
具體步驟:
- 首先,記錄下兩個數(shù)組的長度大小,以備后序的計算中位數(shù)做準備;
- 為了防止分區(qū)點的在第二個數(shù)組的兩側(cè)都有元素,導(dǎo)致出現(xiàn)數(shù)組越界的現(xiàn)象。在此實現(xiàn)中,我們首先檢查第一個數(shù)組的長度是否大于第二個數(shù)組的長度。如果是,我們交換數(shù)組以確保第一個數(shù)組始終是較短的那個數(shù)組;
- 然后,我們使用二叉搜索來查找兩個數(shù)組的分區(qū)點,我們計算分區(qū)點。使得兩個數(shù)組中分區(qū)左側(cè)的元素數(shù)小于分區(qū)右側(cè)的元素數(shù);
- 找到較短數(shù)組的分區(qū)點partition1,利用公式找到較長數(shù)組的分區(qū)點partition2;
- 然后我們檢查分區(qū)點是否在數(shù)組的邊界,如果沒有,我們檢查分區(qū)點處元素是否形成有效的中位數(shù);?如果沒有,我們可以相應(yīng)的調(diào)整分區(qū)點;
- 如果分區(qū)點位于數(shù)組的邊界或者分區(qū)點處的元素形成有效的中位數(shù),我們可以計算兩個數(shù)組的中位數(shù);
- 然后,我們計算兩個數(shù)組中分區(qū)左側(cè)的最大元素和兩個數(shù)組中分區(qū)右側(cè)的最小元素,如果較短數(shù)組中分區(qū)左側(cè)的最大元素小于或等于較長數(shù)組中分區(qū)右側(cè)的最小元素 ,并且?較短數(shù)組中分區(qū)右側(cè)的最小元素大于等于較長數(shù)組中分區(qū)左側(cè)的最大元素?,然后表明我們找到了中位數(shù);
- 如果合并后數(shù)組的長度是偶數(shù),我們?nèi)》謪^(qū)左側(cè)最大元素和分區(qū)右側(cè)最小元素的平均值;如果合并后數(shù)組的長度是奇數(shù),我們?nèi)》謪^(qū)左側(cè)最大元素作為作為中位數(shù)
代碼如下:
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
//記錄兩個數(shù)組的長度大小
int m = nums1.size();
int n = nums2.size();
//確保第一個數(shù)組始終是較短數(shù)組
if (m > n)
{
return findMedianSortedArrays(nums2, nums1);
}
//在較短數(shù)組的區(qū)間 【0,m】之間里查找出合適的分區(qū)點
//使得較短數(shù)組滿足我們需要的條件
int left = 0;
int right = m;
while (left <= right) {
//找到較短數(shù)組的分區(qū)點partition1
int partition1 = (left + right) / 2;
//利用公式找到較長數(shù)組的分區(qū)點partition2
int partition2 = (m + n + 1) / 2 - partition1;
//然后我們檢查分區(qū)點是否在數(shù)組的邊界,如果沒有,我們檢查分區(qū)點處元素是否形成有效的中位數(shù)
//如果沒有,我們可以相應(yīng)的調(diào)整分區(qū)點
//較短數(shù)組找到分區(qū)點后,因為數(shù)組是已經(jīng)排好序的
//當 partition1=0 時,說明較小數(shù)組分割線左邊沒有值,為了不影響
//nums1[partition1] <= nums2[partition2]和 Math.max(maxLeft1, maxLeft2)的判斷
//所以將它設(shè)置為int的最小值,即INT_MIN
int maxLeft1 = (partition1 == 0) ? INT_MIN : nums1[partition1 - 1];
//較短數(shù)組找到分區(qū)點后,因為數(shù)組是已經(jīng)排好序的
//partition1 等于較小數(shù)組的長度時,說明較小數(shù)組分割線右邊沒有值,為了不影響
// nums2[partition2] <= nums1[partition1] 和 Math.min(minRight1, minRight2)的判斷,
//所以將它設(shè)置為int的最大值,即INT_MAX
int minRight1 = (partition1 == m) ? INT_MAX : nums1[partition1];
//較長數(shù)組找到分區(qū)點后,因為數(shù)組是已經(jīng)排好序的
//當partition2等于0時,說明較長數(shù)組分割線左邊沒有值,為了不影響
// nums2[partition2] <= nums1[partition1] 和 Math.max(maxLeft1, maxLeft2)的判斷,
//所以將它設(shè)置為int的最小值,即INT_MIN
int maxLeft2 = (partition2 == 0) ? INT_MIN : nums2[partition2 - 1];
//較長數(shù)組找到分區(qū)點后,因為數(shù)組是已經(jīng)排好序的
//當partition2 == n,說明較長數(shù)組分割線右邊沒有值,為了不影響
//nums1[partition1] <= nums2[partition2] 和 Math.min(minRight1, minRight2)的判斷,
//所以將它設(shè)置為int的最大值,即INT_MAX
int minRight2 = (partition2 == n) ? INT_MAX : nums2[partition2];
//然后,我們計算兩個數(shù)組中分區(qū)左側(cè)的最大元素和兩個數(shù)組中分區(qū)右側(cè)的最小元素
//如果較短數(shù)組中分區(qū)左側(cè)的最大元素小于或等于較長數(shù)組中分區(qū)右側(cè)的最小元素 并且
//較短數(shù)組中分區(qū)右側(cè)的最小元素大于等于較長數(shù)組中分區(qū)左側(cè)的最大元素 ,然后表明我們找到了中位數(shù)
if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
//如果合并后數(shù)組的長度是偶數(shù),我們?nèi)》謪^(qū)左側(cè)最大元素和分區(qū)右側(cè)最小元素的平均值
if ((m + n) % 2 == 0)
{
return (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2.0;
}
//如果合并后數(shù)組的長度是奇數(shù),我們?nèi)》謪^(qū)左側(cè)最大元素作為作為中位數(shù)
else
{
return max(maxLeft1, maxLeft2);
}
}
//此處用了maxleft1 < minRight2的取反,當較小數(shù)組中分區(qū)點的左邊的值大于較長數(shù)組中分區(qū)點的右邊的值
//表面右指針應(yīng)該左移
else if (maxLeft1 > minRight2)
{
right = partition1 - 1;
}
//滿足條件,左指針繼續(xù)右移到 partition1 + 1位置處
else
{
left = partition1 + 1;
}
}
return 0.0;
}
};
性能分析:文章來源:http://www.zghlxwxcb.cn/news/detail-426681.html
- ?時間復(fù)雜度:O(logmin(m,n))),其中?m 和?n 分別是數(shù)組?nums1?和?nums2的長度。查找的區(qū)間是?[0,m],而該區(qū)間的長度在每次循環(huán)之后都會減少為原來的一半。所以,只需要執(zhí)行?logm 次循環(huán)。由于每次循環(huán)中的操作次數(shù)是常數(shù),所以時間復(fù)雜度為?O(logm)。由于我們可能需要交換?nums1?和?nums?2 使得?m≤n,因此時間復(fù)雜度是?O(logmin(m,n)))。
- 空間復(fù)雜度:因為不需要借助額外的空間,因此 空間復(fù)雜度為O(1)。
到此,本題便講解結(jié)束了??!文章來源地址http://www.zghlxwxcb.cn/news/detail-426681.html
到了這里,關(guān)于《LeetCode 熱題 HOT 100》——尋找兩個正序數(shù)組的中位數(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容,請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章,希望大家以后多多支持TOY模板網(wǎng)!