median

admin管理员组

文章数量:1794759

median

排序的代价过于高，我们可以采用挪动指针的方法找到第k大的值
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)).
参考了大神的代码：

#include <iostream>
#include <map>
#include <string>
using namespace std;class Solution {
public:double findMedianSortedArrays(int A[], int m,int B[], int n) {int k = (m+n)%2;if (k==0) return (f(A,m,B,n,(m+n)/2)+f(A,m,B,n,(m+n)/2+1))/2;else return f(A,m,B,n,(m+n)/2+1);}
};double f(int a[],int m,int b[],int n,int k) {if(m>n) return f(b,n,a,m,k);if(m==0) return b[k-1];if(k==1) return min(a[0],b[0]);int pa = min(k/2,m),pb = k-pa;if(a[pa-1]<b[pb-1]) {return f(a+pa,m-pa,b,n,k-pa);}else if(b[pb-1]<a[pa-1]) {return f(a,m,b+pb,n-pb,k-pb);}else return b[pb-1];
}

本文标签： median