国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[LintCode/LeetCode] Median of two Sorted Arrays

vvpvvp / 1830人閱讀

摘要:由于要求的時間,所以選擇二分法。思路是找到兩個數組合并起來的第個元素。這樣只需計算兩個數組的中位數是第幾個元素,代入功能函數即可。據此,根據二分法的性質,我們在遞歸時可以將前即個元素排除。

Problem

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays.

Example

Given A=[1,2,3,4,5,6] and B=[2,3,4,5], the median is 3.5.

Given A=[1,2,3] and B=[4,5], the median is 3.

Challenge

The overall run time complexity should be O(log (m+n)).

Note

由于要求O(log(m+n))的時間,所以選擇二分法。
思路是找到兩個數組合并起來的第k個元素。這樣,只需計算兩個數組的中位數是第幾個元素,代入功能函數即可。當然,這里要先判斷總長度的奇偶性,若為奇數,則取中間的元素;若為偶數,則計算中間兩個數的平均值。

有兩點需要注意:
在功能函數findKth()中,雖然是尋找第k個元素,但是對應數組的順序是k-1,
由于二分搜索需要不斷遞歸,所以極限情況是k1的時候,此時要返回AB中首元素較小的那個。

二分搜索第k個元素的原理:
首先,找到k個元素的中點mid,令mid = k/2-1
假設數組A和B的長度都大于首元素加上mid個元素的長度,那么,對于我們的數組A的前mid個元素和數組B的前mid個元素,一定不包含要找的第k個元素。
據此,根據二分法的性質,我們在遞歸時可以將前mid+1(即k/2)個元素排除。
那么,排除A還是B的前mid+1個元素呢?
比較一下A和B的第mid+1個元素,哪個小就排除該數組的前mid+1個元素。
然后,繼續遞歸查找第k-k/2個元素。

Solution
    class Solution {
        public double findMedianSortedArrays(int[] A, int[] B) {
            int len = A.length + B.length;
            if (len % 2 == 0) return (findKth(A, 0, B, 0, len/2)+findKth(A, 0, B, 0, len/2+1))/2.0;
            else return findKth(A, 0, B, 0, len/2+1);
        }
        public double findKth(int[] A, int Astart, int[] B, int Bstart, int k) {
            if (Astart == A.length) return B[Bstart+k-1];
            else if (Bstart == B.length) return A[Astart+k-1];
            if (k == 1) return Math.min(A[Astart], B[Bstart]);
            int mid = k/2-1, kNew = k-k/2, kA = Integer.MAX_VALUE, kB = kA;
            if (Astart + mid < A.length) kA = A[Astart+mid];
            if (Bstart + mid < B.length) kB = B[Bstart+mid];
            if (kA < kB) return findKth(A, Astart+k/2, B, Bstart, kNew);
            else return findKth(A, Astart, B, Bstart+k/2, kNew);
        }
    }
Naive method: O(m+n) time
public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n1 = nums1.length, n2 = nums2.length;
        int len = n1+n2;
        if (len%2 == 0) return (find(nums1, nums2, len/2)+find(nums1, nums2, len/2+1))/2.0;
        else return (double)find(nums1, nums2, len/2+1);
    }
    public int find(int[] A, int[] B, int k) {
        int res = 0;
        int i = 0, j = 0;
        while (k != 0 && i < A.length && j < B.length) {
            if (A[i] < B[j]) res = A[i++];
            else res = B[j++];
            k--;
        }
        if (k != 0) {
            if (i < A.length) res = A[i+k-1];
            else res = B[j+k-1];
        }
        return res;
    }
}
Update 2018.8
//沒有使用二分法我覺得是一種退步
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int totalLength = nums1.length + nums2.length;
        int[] nums = new int[totalLength];
        int i = 0, j = 0, k = 0;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] <= nums2[j]) {
                nums[k++] = nums1[i++];
            } else {
                nums[k++] = nums2[j++];
            }
        }
        while (i < nums1.length) {
            nums[k++] = nums1[i++];
        }
        while (j < nums2.length) {
            nums[k++] = nums2[j++];
        }
        if (totalLength % 2 == 0) {
            return (double) (nums[totalLength/2-1] + nums[totalLength/2])/2;
        } else {
            return (double) nums[totalLength/2];
        }
    }
}

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

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

相關文章

  • [LintCode/LeetCode] Find Median From / Data Stream

    摘要:建立兩個堆,一個堆就是本身,也就是一個最小堆另一個要寫一個,使之成為一個最大堆。我們把遍歷過的數組元素對半分到兩個堆里,更大的數放在最小堆,較小的數放在最大堆。同時,確保最大堆的比最小堆大,才能從最大堆的頂端返回。 Problem Numbers keep coming, return the median of numbers at every time a new number a...

    zxhaaa 評論0 收藏0
  • leetcode長跑】開個頭 Median of Two Sorted Arrays

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

    荊兆峰 評論0 收藏0
  • Leetcode[4] Median of two sorted arrays

    摘要:復雜度思路因為要找中位數,又是在兩個的數組里面。所以考慮用二分法。二分法經常適合的接下來考慮如何二分。然后對和進行比較,記為和。所以為了縮小搜索范圍,我們可以扔掉這些數,在的剩下來的數中和的數組中接著找。說明中沒有個數可以尋找。 Leetcode[4] Median of two sorted arrays There are two sorted arrays nums1 and n...

    sarva 評論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 評論0 收藏0
  • [LintCode/LeetCode] Merge Sorted Array

    Problem Given two sorted integer arrays A and B, merge B into A as one sorted array. Notice You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements ...

    summerpxy 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<