資訊專欄INFORMATION COLUMN
摘要：復雜度思路因為要找中位數(shù)，又是在兩個的數(shù)組里面。所以考慮用二分法。二分法經(jīng)常適合的接下來考慮如何二分。然后對和進行比較，記為和。所以為了縮小搜索范圍，我們可以扔掉這些數(shù)，在的剩下來的數(shù)中和的數(shù)組中接著找。說明中沒有個數(shù)可以尋找。
Leetcode[4] Median of two sorted arrays
There are two sorted arrays nums1 and nums2 of size m and nBinary search
respectively.Find the median of the two sorted arrays. The overall run time
complexity should be O(log (m+n)).Example 1: nums1 = [1, 3] nums2 = [2]
The median is 2.0 Example 2: nums1 = [1, 2] nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
復雜度
O(lg(m + n))
思路
因為要找中位數(shù)，又是在兩個sorted的數(shù)組里面。所以考慮用二分法。（二分法經(jīng)常適合sorted的array).
接下來考慮如何二分。
假設(shè)第k個數(shù)是我們要找的中位數(shù)，那么前k-1個數(shù)應(yīng)該都比這個第k個數(shù)要小。后面的數(shù)都比這個第k個數(shù)大。（像變形的用二分法找第K個數(shù)）。
如果我們每次在a數(shù)組中找前(k/2) = m個數(shù)，在b數(shù)組中找剩下的(k-k/2) = n個數(shù)。然后對a[p + k/2 - 1]和b[q + k - k/2 -1]進行比較，記為a[i]和b[j]。
a[i] < b[j]： 說明我們可以扔掉0-i之間的（i+ 1）個數(shù)。為什么？
因為a數(shù)組中的前m個數(shù)的最大值都比b數(shù)組中的前n個數(shù)要小，那么這前m個數(shù)一定是在我們想要的中位數(shù)之前的，并且對找到中位數(shù)沒有說明影響。所以為了縮小搜索范圍，我們可以扔掉這些數(shù)，在a的剩下來的數(shù)中和b的數(shù)組中接著找。
i>=a.length: 說明a中沒有m個數(shù)可以尋找。那么第K個數(shù)要么在b剩下的數(shù)組[n ~ b.length]中，要么就在a的前m個數(shù)中。
一直搜索到什么時候為止呢？
k=1代表的是，當前的這個是就是我們想要的值，我們應(yīng)該在如何選擇? Math.min(a[p], b[q]).
if(a[i] < b[j]) {
search（a[right], b[0], k - m);
} else {
search (a[0], b[right], k - n);
}
我們從找第K個數(shù)開始，一直到K=1，每次扔掉一部分數(shù) k /2，所以時間復雜度是log(k).
K=(M + N) / 2, 所以時間復雜度是log(m + n)
代碼
class Solution {
// 其實找的是第k個值。
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len = nums1.length + nums2.length;
if(len % 2 == 0) {
return findKthNumberInTwoArray(nums1, nums2, 0, 0, len / 2) / 2
+ findKthNumberInTwoArray(nums1, nums2, 0, 0, len / 2 + 1) / 2;
} else {
return findKthNumberInTwoArray(nums1, nums2, 0, 0, len / 2 + 1);
}
}
// p is the start index of nums1, q is the start index of nums2, we wanna find the kth number
// in both num1 & nums2
public double findKthNumberInTwoArray(int[] nums1, int[] nums2, int p, int q, int k) {
if(p >= nums1.length) return nums2[q + k - 1];
if(q >= nums2.length) return nums1[p + k - 1];
if(k == 1) return Math.min(nums1[p], nums2[q]);
int m = k / 2, n = k - m;
// 因為當a數(shù)組沒有中這個數(shù)的時候，說明第k一定在b數(shù)組剩余的數(shù)中和a數(shù)組的剩余數(shù)組中的一個。
int aVal = Integer.MAX_VALUE, bVal = Integer.MAX_VALUE;
if(p + m - 1 < nums1.length) aVal = nums1[p + m - 1];
if(q + n - 1 < nums2.length) bVal = nums2[q + n - 1];
if(aVal < bVal) {
return findKthNumberInTwoArray(nums1, nums2, p + m, q, k - m);
} else {
return findKthNumberInTwoArray(nums1, nums2, p, q + n, k - n);
}
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/68357.html
摘要：自第一篇收集向的文章發(fā)布后，近年半沒更新這個專欄了。今天是分類中第一個的，叫做。不過這樣需要兩個數(shù)組各掃一遍，然而我們的目的只是要取到中間值，似乎并不用完整的掃一遍。那么也就意味著，我們最終要記錄的值可能是兩個。 大家好，我叫張小豬。 自第一篇收集向的文章發(fā)布后，近 1 年半沒更新這個專欄了。最近面試中發(fā)現(xiàn)將近 60% 的候選人對于 bubble sort 面露難色，于是心悸于自己也忘...
摘要：解法解法應(yīng)該是最常見的一種解法，就是將兩個數(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ù)是第幾個元素，代入功能函數(shù)即可。據(jù)此，根據(jù)二分法的性質(zhì)，我們在遞歸時可以將前即個元素排除。 Problem There are two sorted arrays A and B 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...
摘要：最新解法及思路有兩個有序數(shù)組和，他們的大小各是和，請找出這兩個數(shù)組所有數(shù)的中位數(shù)，總得時間復雜度不超過歸并計數(shù)法復雜度時間空間思路如果對時間復雜度沒有要求，這個方法是實現(xiàn)起來最簡單的，我們只需要從下往上依次數(shù)個元素即可。 Median of Two Sorted Arrays 最新解法及思路：https://yanjia.li/zh/2018/11/... There are two...
閱讀 1003·2023-04-26 01:47
閱讀 1683·2021-11-18 13:19
閱讀 2050·2019-08-30 15:44
閱讀 665·2019-08-30 15:44
閱讀 2306·2019-08-30 15:44
閱讀 1242·2019-08-30 14:06
閱讀 1429·2019-08-30 12:59
閱讀 1907·2019-08-29 12:49
