首页 > 代码库 > LeetCode Median of Two Sorted Arrays
LeetCode Median of Two Sorted Arrays
There are two sorted arrays A and B 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)).
Show Tags
题意：求两个有序数组的组成一个新的数组的中位数
思路：题目转换为求第k大的数，如果总个数是奇数的话，就是求第中间的数了，如果是偶数的话，就是找到两个中间的，求平均数。
求第k大的数：首先假设我们求的是两个数组A和B中第k个数，为了我们每次都能折半查找，每次尽量使得两个数组平分k/2，那么我们每次都能比较每个数组能都对应到自身的k/2-1的
的值，如果A[k/2-1]<B[k/2-1]的话，说明的是A数组的前k个数字都是在最后数组的前k个中，那么就可以裁掉一点了，依次类推
class Solution {
public:
double findMedianSortedArrays(int A[], int m, int B[], int n) {
int size = m + n;
int k = (m + n + 1) / 2;
if (size & 1)
return findKth(A, m, B, n, k);
else return (findKth(A, m, B, n, k) + findKth(A, m, B, n, k+1)) / 2;
}
double findKth(int A[], int m, int B[], int n, int k) {
if (m > n)
return findKth(B, n, A, m, k);
if (m == 0)
return B[k - 1];
if (k == 1)
return A[0] < B[0] ? A[0] : B[0];
int index = k / 2;
int left = index < m ? index : m;
int right = k - left;
if (A[left - 1] < B[right - 1])
return findKth(A + left, m - left, B, n, right);
else if (A[left - 1] > B[right - 1])
return findKth(A, m, B + right, n - right, left);
else return A[left - 1];
}
};LeetCode Median of Two Sorted Arrays
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。