leetcode 4:两个排序数组的中位数

本文主要是介绍leetcode 4:两个排序数组的中位数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

寻找中位数，当m+n是奇数时，中位数为第（m+n+1）/2个数,当m+n为偶数时，中位数为第（m+n+1）/2和（m+n+2）/2的平均数

根据整数的取整，我们可以统一为中位数为第（m+n+1）/2和（m+n+2）/2的平均数。

如何使用二分法求两个有序数组的第k个数

首先将数组A和数组B分为left_A(下标为0~k/2-1),right_A,left_B(下标为0~k/2-1),right_B

如果left[k/2-2]>right[k/2] 第k个值在left_A,right_A,right_B中

反之，第k个值在left_B,right_A,right_B中

int getKth(int* ln, int m, int* rn, int n, int k) {if (m > n) {return getKth(rn, n, ln, m, k);}if (m == 0) {return rn[k - 1];}if (k == 1) {return std::min(ln[0], rn[0]);}int i = std::min(m, k / 2), j = std::min(n, k / 2);if (ln[i - 1] > rn [j - 1]) {return getKth(ln, m, rn + j, n - j, k - j);} else {return getKth(ln + i, m - i, rn, n, k - i);}
}
double findMedianSortedArrays(std::vector<int>& nums1, std::vector<int>& nums2) {int m = nums1.size();int n = nums2.size();int l=(m+n+1)/2;int r=(m+n+2)/2;int *ln=m>0?&nums1[0]:NULL;int *rn=n>0?&nums2[0]:NULL;return (getKth(ln,m,rn,n,l)+getKth(ln,m,rn,n,r))/2.0;
}

 

这篇关于leetcode 4:两个排序数组的中位数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---