Leetcode[4] Median of two sorted arrays

sarva 發布于2019-08-15 13:51 / 2650人閱讀

摘要：復雜度思路因為要找中位數，又是在兩個的數組里面。所以考慮用二分法。二分法經常適合的接下來考慮如何二分。然后對和進行比較，記為和。所以為了縮小搜索范圍，我們可以扔掉這些數，在的剩下來的數中和的數組中接著找。說明中沒有個數可以尋找。

Leetcode[4] 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)).
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

Binary search

復雜度
O(lg(m + n))

思路
因為要找中位數，又是在兩個sorted的數組里面。所以考慮用二分法。（二分法經常適合sorted的array).
接下來考慮如何二分。
假設第k個數是我們要找的中位數，那么前k-1個數應該都比這個第k個數要小。后面的數都比這個第k個數大。（像變形的用二分法找第K個數）。
如果我們每次在a數組中找前(k/2) = m個數，在b數組中找剩下的(k-k/2) = n個數。然后對a[p + k/2 - 1]和b[q + k - k/2 -1]進行比較，記為a[i]和b[j]。

a[i] < b[j]：說明我們可以扔掉0-i之間的（i+ 1）個數。為什么？
因為a數組中的前m個數的最大值都比b數組中的前n個數要小，那么這前m個數一定是在我們想要的中位數之前的，并且對找到中位數沒有說明影響。所以為了縮小搜索范圍，我們可以扔掉這些數，在a的剩下來的數中和b的數組中接著找。

i>=a.length: 說明a中沒有m個數可以尋找。那么第K個數要么在b剩下的數組[n ~ b.length]中，要么就在a的前m個數中。

一直搜索到什么時候為止呢？
k=1代表的是，當前的這個是就是我們想要的值，我們應該在如何選擇? 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個數開始，一直到K=1，每次扔掉一部分數 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數組沒有中這個數的時候，說明第k一定在b數組剩余的數中和a數組的剩余數組中的一個。
        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);
        }
    }
}

GPU云服務器云服務器 sorted-array Median LeetCode two

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/68357.html

【leetcode長跑】開個頭 Median of Two Sorted Arrays

摘要：自第一篇收集向的文章發布后，近年半沒更新這個專欄了。今天是分類中第一個的，叫做。不過這樣需要兩個數組各掃一遍，然而我們的目的只是要取到中間值，似乎并不用完整的掃一遍。那么也就意味著，我們最終要記錄的值可能是兩個。大家好，我叫張小豬。自第一篇收集向的文章發布后，近 1 年半沒更新這個專欄了。最近面試中發現將近 60% 的候選人對于 bubble sort 面露難色，于是心悸于自己也忘...

荊兆峰 2019-08-21 17:24 評論0 收藏0
Leetcode-4 Median of Two Sorted Arrays

摘要：解法解法應該是最常見的一種解法，就是將兩個數組頭尾相加合并起來，然后重新排序，例如輸入兩個數組，合并之后變為，然后求出中位數。如果兩個數組長度和為偶數，那么中位數有兩個，否則只有一個題目 There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the tw...

Shihira 2019-08-16 13:50 評論0 收藏0
[LintCode/LeetCode] Median of two Sorted Arrays

摘要：由于要求的時間，所以選擇二分法。思路是找到兩個數組合并起來的第個元素。這樣只需計算兩個數組的中位數是第幾個元素，代入功能函數即可。據此，根據二分法的性質，我們在遞歸時可以將前即個元素排除。 Problem There are two sorted arrays A and B of size m and n respectively. Find the median of the tw...

vvpvvp 2019-08-14 15:41 評論0 收藏0
Leetcode 4 Median of Two Sorted Arrays 兩排序數組的中位數

摘要：難度為這個題目描述很清晰給出兩個排序好的數組求這兩個數組的中位數在解這個題的過程中會碰到以下的問題先合起來重新排序是不可行的時間復雜度太高為先歸并排序也是不可行的時間復雜度為用類似桶排的方法時間復雜度為不可行可能會碰到多種全部大于或全部小于 There are two sorted arrays nums1 and nums2 of size m and n respectively...

wudengzan 2019-08-14 17:05 評論0 收藏0
[Leetcode] Median of Two Sorted Arrays 有序數組中位數

摘要：最新解法及思路有兩個有序數組和，他們的大小各是和，請找出這兩個數組所有數的中位數，總得時間復雜度不超過歸并計數法復雜度時間空間思路如果對時間復雜度沒有要求，這個方法是實現起來最簡單的，我們只需要從下往上依次數個元素即可。 Median of Two Sorted Arrays 最新解法及思路：https://yanjia.li/zh/2018/11/... There are two...

wuaiqiu 2019-08-14 12:17 評論0 收藏0