資訊專欄INFORMATION COLUMN
摘要：自第一篇收集向的文章發(fā)布后，近年半沒更新這個(gè)專欄了。今天是分類中第一個(gè)的，叫做。不過這樣需要兩個(gè)數(shù)組各掃一遍，然而我們的目的只是要取到中間值，似乎并不用完整的掃一遍。那么也就意味著，我們最終要記錄的值可能是兩個(gè)。
大家好，我叫張小豬。
自第一篇收集向的文章發(fā)布后，近 1 年半沒更新這個(gè)專欄了。最近面試中發(fā)現(xiàn)將近 60% 的候選人對(duì)于 bubble sort 面露難色，于是心悸于自己也忘記了很多大學(xué)的內(nèi)容，遂有時(shí)間就寫寫 leetcode 好了，也不荒廢當(dāng)初開了這個(gè)地方。路途遙遠(yuǎn)，且行且珍惜。
今天是 Algorithms 分類中第一個(gè) Hard 的，叫做 Median of Two Sorted Arrays。描述如下：
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)).
題目描述內(nèi)容比較少，大意就是提供兩個(gè)有序數(shù)組，需要找到這兩個(gè)數(shù)組的中間值。
給了兩個(gè)例子:
nums1 = [1, 3] nums2 = [2] The median is 2.0
nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5
看完描述和例子后，第一反應(yīng)就是合并兩個(gè)數(shù)組，然后找到中間位置即可。不過這樣需要兩個(gè)數(shù)組各掃一遍，然而我們的目的只是要取到中間值，似乎并不用完整的掃一遍。那就按照這個(gè)思路看看吧。
首先，根據(jù)例子可以看出，偶數(shù)和奇數(shù)個(gè)長度對(duì)于最終結(jié)果的計(jì)算是會(huì)有影響的。即奇數(shù)個(gè)我們能直接取到中間值，而偶數(shù)個(gè)需要取到最靠近中間的兩個(gè)值然后取平均數(shù)。那么也就意味著，我們最終要記錄的值可能是兩個(gè)。
然后，由于兩個(gè)數(shù)組都是有序的，那么他們的中間值索引其實(shí)就是做合并操作過程中的索引。
基于以上兩點(diǎn)，我們得到要做的事情是:
計(jì)算中間值的索引
做有序數(shù)組合并
得到結(jié)果
那么開始寫代碼吧（吐槽一下 leetcode 的編輯器并不太好用）:
var findMedianSortedArrays = function(nums1, nums2) {
var sumLen = nums1.length + nums2.length,
targetLen = sumLen >>> 1,
loop = targetLen + 1,
i = 0, // for num1 index
j = 0, // for num2 index
x, y;
while (loop--) {
x = y;
if (nums1[i] === undefined) {
y = nums2[j++]
} else if (nums2[j] === undefined) {
y = nums1[i++];
} else if (nums1[i] < nums2[j]) {
y = nums1[i++];
} else {
y = nums2[j++];
}
}
return targetLen << 1 === sumLen ? (x + y) / 2 : y;
};
Test case 通過后連續(xù)提交了幾次，時(shí)間在 beats 85% 左右浮動(dòng)，最低 72%，最高 97%，算是可以接受吧。
想想最近快要到雙 11 了，別人都是買包買衣買香水、家具電器旅行飛，小豬只是連著關(guān)注了幾天顯卡和 CPU，還舍不得剁手。哎，說多了都是淚啊，還是洗洗豬鼻子睡了吧。。。
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/89481.html
摘要：復(fù)雜度思路因?yàn)橐抑形粩?shù)，又是在兩個(gè)的數(shù)組里面。所以考慮用二分法。二分法經(jīng)常適合的接下來考慮如何二分。然后對(duì)和進(jìn)行比較，記為和。所以為了縮小搜索范圍，我們可以扔掉這些數(shù)，在的剩下來的數(shù)中和的數(shù)組中接著找。說明中沒有個(gè)數(shù)可以尋找。 Leetcode[4] Median of two sorted arrays There are two sorted arrays nums1 and n...
摘要：解法解法應(yīng)該是最常見的一種解法，就是將兩個(gè)數(shù)組頭尾相加合并起來，然后重新排序，例如輸入兩個(gè)數(shù)組，合并之后變?yōu)椋缓笄蟪鲋形粩?shù)。如果兩個(gè)數(shù)組長度和為偶數(shù)，那么中位數(shù)有兩個(gè)，否則只有一個(gè) 題目 There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the tw...
摘要：由于要求的時(shí)間，所以選擇二分法。思路是找到兩個(gè)數(shù)組合并起來的第個(gè)元素。這樣只需計(jì)算兩個(gè)數(shù)組的中位數(shù)是第幾個(gè)元素，代入功能函數(shù)即可。據(jù)此，根據(jù)二分法的性質(zhì)，我們?cè)谶f歸時(shí)可以將前即個(gè)元素排除。 Problem There are two sorted arrays A and B of size m and n respectively. Find the median of the tw...
摘要：最新解法及思路有兩個(gè)有序數(shù)組和，他們的大小各是和，請(qǐng)找出這兩個(gè)數(shù)組所有數(shù)的中位數(shù)，總得時(shí)間復(fù)雜度不超過歸并計(jì)數(shù)法復(fù)雜度時(shí)間空間思路如果對(duì)時(shí)間復(fù)雜度沒有要求，這個(gè)方法是實(shí)現(xiàn)起來最簡單的，我們只需要從下往上依次數(shù)個(gè)元素即可。 Median of Two Sorted Arrays 最新解法及思路：https://yanjia.li/zh/2018/11/... There are two...
摘要：難度為這個(gè)題目描述很清晰給出兩個(gè)排序好的數(shù)組求這兩個(gè)數(shù)組的中位數(shù)在解這個(gè)題的過程中會(huì)碰到以下的問題先合起來重新排序是不可行的時(shí)間復(fù)雜度太高為先歸并排序也是不可行的時(shí)間復(fù)雜度為用類似桶排的方法時(shí)間復(fù)雜度為不可行可能會(huì)碰到多種全部大于或全部小于 There are two sorted arrays nums1 and nums2 of size m and n respectively...
閱讀 1332·2021-10-27 14:14
閱讀 3584·2021-09-29 09:34
閱讀 2488·2019-08-30 15:44
閱讀 1733·2019-08-29 17:13
閱讀 2577·2019-08-29 13:07
閱讀 880·2019-08-26 18:26
閱讀 3351·2019-08-26 13:44
閱讀 3217·2019-08-26 13:37
