資訊專欄INFORMATION COLUMN
摘要：題目解答方法一由于兩個數(shù)組都是排好序的，因此首先可以想到的思路就是利用歸并排序把兩個數(shù)組合并成一個有序的長數(shù)組，然后直接取出中位數(shù)即可。如果滿足條件，則直接返回求取中位數(shù)。如果減小，則增加，左邊序列數(shù)組的值會更小，右邊序列數(shù)組的值會更大。
1. 題目 2. 解答
由于兩個數(shù)組都是排好序的，因此首先可以想到的思路就是利用歸并排序把兩個數(shù)組合并成一個有序的長數(shù)組，然后直接取出中位數(shù)即可。
class Solution:
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
len1 = len(nums1)
len2 = len(nums2)
nums = []
i = 0
j = 0
while (i < len1 and j < len2):
if (nums1[i] <= nums2[j]):
nums.append(nums1[i])
i += 1
else:
nums.append(nums2[j])
j += 1
if (i < len1):
while(i < len1):
nums.append(nums1[i])
i += 1
if (j < len2):
while(j < len2):
nums.append(nums2[j])
j += 1
odd = (len1 + len2) % 2 # 長度是否為奇數(shù)
mid = (len1 + len2 - 1) // 2
if (odd):
return nums[mid]
else:
return (nums[mid] + nums[mid+1]) / 2
因為要遍歷兩個數(shù)組，所以時間復雜度為 $O(m+n)$，而題目中要求算法的時間復雜度為 $O(log (m+n))$，因此應該是有更高效的算法，借助于二分查找。
所謂中位數(shù)，就是將 K 個數(shù)據(jù)分為長度相等的兩組，左邊的數(shù)據(jù)小于等于右邊的數(shù)據(jù)。
如果我們要在任意位置 $i$ 處將長度為 $m$ 的數(shù)組 $A$ 分為兩部分，則共有 $m+1$ 種分法，$i=[0, m]$。
$$ left\_part quad | quad right\_part$$
$$ A[0], A[1], ..., A[i-1] quad | quad A[i], A[i+1], ..., A[m-1]$$
$i=0$ 說明左半部分沒有元素，反之 $i=m$ 說明右半部分沒有元素。左半邊元素個數(shù)為 $i$ ，右半邊元素個數(shù)為$m-i$。
同理，我們可以在任意位置 $j$ 處將長度為 $n$ 的數(shù)組 $B$ 分為兩部分，則共有 $n+1$ 種分法，$j=[0, n]$。
$$ B[0], B[1], ..., B[j-1] quad | quad B[j], B[j+1], ..., B[n-1]$$
針對劃分完后的數(shù)組 $A$ 和 $B$，如果滿足：
左邊部分的長度等于右邊部分的長度（偶數(shù)情況），$i+j = m-i + n-j$；或者等于右邊部分的長度加 1（奇數(shù)情況） ,$i+j = m-i + n-j+1$。
左邊的最大元素小于等于右邊的最小元素，$A[i-1] <= B[j] quad and quad B[i-1] <= A[j]$。
那我們也就找到了中位數(shù)，$median = frac{max(left\_part) + min(right\_part)}{2}$。
所以，我們要做的就是在 $i=[0, m]$ 區(qū)間搜索一個 $i$ 值，使得上面的條件得到滿足。也即
$$ A[i-1] <= B[j] quad and quad B[i-1] <= A[j] ，其中 quad j = frac{m+n+[1]}{2}-i$$
加不加 1 取決于總的長度是奇數(shù)還是偶數(shù)，同時，為了保證 $j$ 的范圍在 $[0, n]$，我們必須要求 $n <= m$。
接下來，我們就在 $i=[0, m]$ 區(qū)間進行二分查找。
如果滿足條件，則直接返回求取中位數(shù)。
如果 $i > 0 quad and quad A[i-1] > B[j]$，則減小 $i$。如果增加 $i$，則 $j$ 減小，左邊序列數(shù)組 $A$ 的值會更大，右邊序列數(shù)組 $B$ 的值會更小。
如果 $i < m quad and quad B[i-1] > A[j]$，則增加 $i$。如果減小 $i$，則 $j$ 增加，左邊序列數(shù)組 $A$ 的值會更小，右邊序列數(shù)組 $B$ 的值會更大。
最后，我們求得左半部分的最大值以及右半部分的最小值，然后就可以求出中位數(shù)了。
因為，要查找的范圍為 $i=[0, m]$，而且每次查找縮小區(qū)間為原來的一半，因此時間復雜度為 $O(log(min(m, n))$，空間復雜度為 $O(1)$。
class Solution {
public:
double findMedianSortedArrays(vector& nums1, vector& nums2) {
int m = nums1.size();
int n = nums2.size();
int len = m + n;
int odd = len % 2;
int left = 0;
int i = 0, j = 0;
vector::iterator A = nums1.begin();
vector::iterator B = nums2.begin();
// 確保數(shù)組 A 的長度小于等于數(shù)組 B 的長度
if (m > n)
{
int temp = m;
m = n;
n = temp;
A = nums2.begin();
B = nums1.begin();
}
int right = m;
while(left <= right)
{
i = left + (right - left) / 2;
j = (len + odd) / 2 - i;
if (i > 0 && A[i-1] > B[j])
{
right = i - 1;
}
else if(i < m && B[j-1] > A[i])
{
left = i + 1;
}
else
{
break;
}
}
int left_max = 0;
int right_min = 0;
// 左半部分的最大值
if (i == 0) left_max = B[j-1];
else if (j == 0) left_max = A[i-1];
else left_max = A[i-1] <= B[j-1] ? B[j-1] : A[i-1];
// 右半部分的最小值
if (i == m) right_min = B[j];
else if (j == n) right_min = A[i];
else right_min = A[i] <= B[j] ? A[i] : B[j];
if (odd)
{
return left_max;
}
else
{
return float(left_max + right_min) / 2;
}
}
};
獲取更多精彩，請關(guān)注「seniusen」!
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/44957.html
摘要：解法解法應該是最常見的一種解法，就是將兩個數(shù)組頭尾相加合并起來，然后重新排序，例如輸入兩個數(shù)組，合并之后變?yōu)椋缓笄蟪鲋形粩?shù)。如果兩個數(shù)組長度和為偶數(shù)，那么中位數(shù)有兩個，否則只有一個 題目 There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the tw...
摘要：難度為這個題目描述很清晰給出兩個排序好的數(shù)組求這兩個數(shù)組的中位數(shù)在解這個題的過程中會碰到以下的問題先合起來重新排序是不可行的時間復雜度太高為先歸并排序也是不可行的時間復雜度為用類似桶排的方法時間復雜度為不可行可能會碰到多種全部大于或全部小于 There are two sorted arrays nums1 and nums2 of size m and n respectively...
摘要：分布式的管理和當我在談?wù)摷軜?gòu)時我在談啥狀態(tài)碼詳解無狀態(tài)協(xié)議和請求支持哪些方法分層協(xié)議棧有哪些數(shù)據(jù)結(jié)構(gòu)運用場景說說你常用的命令為什么要有包裝類面向?qū)ο蟮奶卣魇巧妒巧队惺裁春锰幭到y(tǒng)設(shè)計工程在線診斷系統(tǒng)設(shè)計與實現(xiàn)索引背后的數(shù)據(jù)結(jié)構(gòu)及算法原理軟技能 HTTP 【HTTP】分布式session的管理 【HTTP】Cookie和Session 【HTTP】當我在談?wù)揜estFul架構(gòu)時我在談啥？...
摘要：先去空白，去掉空白之后取第一個字符，判斷正負符號，若是英文直接返回，若數(shù)字則不取。回文數(shù)題目描述判斷一個整數(shù)是否是回文數(shù)。回文數(shù)是指正序從左向右和倒序從右向左讀都是一樣的整數(shù)。 JS算法題之leetcode(1~10) 前言 一直以來，前端開發(fā)的知識儲備在數(shù)據(jù)結(jié)構(gòu)以及算法層面是有所暫缺的，可能歸根于我們的前端開發(fā)的業(yè)務(wù)性質(zhì)，但是我認為任何的編程崗位都離不開數(shù)據(jù)結(jié)構(gòu)以及算法。因此，我作為...
摘要：最新解法及思路有兩個有序數(shù)組和，他們的大小各是和，請找出這兩個數(shù)組所有數(shù)的中位數(shù)，總得時間復雜度不超過歸并計數(shù)法復雜度時間空間思路如果對時間復雜度沒有要求，這個方法是實現(xiàn)起來最簡單的，我們只需要從下往上依次數(shù)個元素即可。 Median of Two Sorted Arrays 最新解法及思路：https://yanjia.li/zh/2018/11/... There are two...
閱讀 525·2023-04-26 00:33
閱讀 3549·2021-11-24 09:39
閱讀 2953·2021-09-22 15:34
閱讀 2325·2019-08-23 18:07
閱讀 2921·2019-08-23 18:04
閱讀 3710·2019-08-23 16:06
閱讀 2902·2019-08-23 15:27
閱讀 1620·2019-08-23 14:32
