[Leetcode]-- Median of Two Sorted Arrays-白红宇

[Leetcode]-- Median of Two Sorted Arrays

阅读量：6081 次

发布时间：2019-06-20

本文共 1667 字，大约阅读时间需要 5 分钟。

public class Solution {        public double findMedianSortedArrays(int A[], int B[]) {                        int aLen = A.length;            int bLen = B.length;                        if((aLen+bLen) % 2 == 0){                return (getKthElement(A, 0, aLen-1, B, 0, bLen-1, (aLen+bLen)/2)                       + getKthElement(A, 0, aLen-1, B, 0, bLen-1, (aLen+bLen)/2 + 1))  / 2.0 ;            } else {                return getKthElement(A, 0, aLen-1, B, 0, bLen-1, (aLen+bLen)/2+1);            }        }            public int getKthElement(int A[], int aBeg, int aEnd, int B[], int bBeg, int bEnd, int k){                                if(aBeg > aEnd){                    return B[bBeg+(k-1)];                }                if(bBeg > bEnd){                    return A[aBeg+(k-1)];                }                                int aMid = (aBeg+aEnd) >>1;                int bMid = (bBeg+bEnd) >>1;                                int len = aMid - aBeg + bMid -bBeg +2;                                if(len > k) {                    if(A[aMid] < B[bMid]){                        return getKthElement(A, aBeg, aEnd, B, bBeg, bMid-1, k);                    }else{                        return getKthElement(A, aBeg, aMid-1, B, bBeg, bEnd, k);                    }                }else {                    if(A[aMid] < B[bMid]){                        return getKthElement(A, aMid+1, aEnd, B, bBeg, bEnd, k - (aMid-aBeg+1));                    } else {                        return getKthElement(A, aBeg, aEnd, B, bMid+1, bEnd, k - (bMid-bBeg+1));                    }                }            }    }

转载于:https://www.cnblogs.com/RazerLu/p/3531128.html

你可能感兴趣的文章