k*********6
发帖数: 738 | 1 我这道题写的程序好ugly啊。能请大牛们share一下漂亮点的解法吗？ | m****i
发帖数: 15 | 2 class Solution {
public:
double fms(int A[], int m, int B[], int n, int k){
if (m>n) {return fms(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);
int pb = k-pa;
if (A[pa-1]<=B[pb-1]) {return fms(A+pa,m-pa,B,n,k-pa);}
return fms(A,m,B+pb,n-pb,k-pb);
}
double findMedianSortedArrays(int A[], int m, int B[], int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int total = m + n;
if(total%2==1){
return fms(A,m,B,n,total/2+1);
}else{
return (fms(A,m,B,n,total/2)+fms(A,m,B,n,total/2+1))/2;
}
}
}; | k*********6
发帖数: 738 | | r*******n
发帖数: 3020 | 4 收藏了
【在 m****i 的大作中提到】
: class Solution {
: public:
: double fms(int A[], int m, int B[], int n, int k){
:
: if (m>n) {return fms(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);
: int pb = k-pa;
| s*****n
发帖数: 994 | 5 class Solution {
public:
double median(int A[], int m){
if (m%2) return A[m/2];
else return 0.5*(A[m/2-1]+A[m/2]);
}
double median(int A[], int m, int val){//m>=2
if (m%2){
if (val
else if (val==A[m/2]) return val;
else return 0.5*(min(A[m/2+1],val)+ A[m/2]);
}else{
if (val < A[m/2-1]) return A[m/2-1];
else if (val > A[m/2]) return A[m/2];
else return val;
}
}
double median(int A[], int m, int small, int big){//m>=3
if (m%2){
if (big<=A[m/2]) return max(big, A[m/2-1]);
else if (small>=A[m/2]) return min(A[m/2+1], small);
else return A[m/2];
}else{
if (big<=A[m/2-1]){
return 0.5*(A[m/2-1] + max(A[m/2-2],big));
}else if (small>=A[m/2]){
return 0.5*(A[m/2] + min(A[m/2+1],small));
}else{
if (big<=A[m/2] && small>=A[m/2-1]){
return 0.5*(small+big);
}else if(big<=A[m/2]){
return 0.5*(A[m/2-1]+big);
}else if(small>=A[m/2-1]){
return 0.5*(A[m/2]+small);
}else{
return 0.5*(A[m/2-1]+A[m/2]);
}
}
}
}
double findMedianSortedArrays(int A[], int m, int B[], int n) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
if (m==0 && n==0) return 0;
if (m==0) return median(B,n);
if (n==0) return median(A,m);
if (m==1 && n==1) return 0.5*(A[0]+B[0]);
if (m==1) return median (B,n, A[0]);
if (n==1) return median (A,m, B[0]);
if (m==2 && n==2) return 0.5*(max(A[0],B[0]) + min(A[1],B[1]));
if (m==2) return median (B,n, A[0], A[1]);
if (n==2) return median (A,m, B[0], B[1]);
int a = A[m/2];
int b = B[n/2];
if (a <= b){
int num_abandom = min (m%2==0?m/2-1:m/2, n-n/2-1);
return findMedianSortedArrays(A+num_abandom, m-num_abandom, B, n
-num_abandom);
}else if (a>b){
int num_abandom = min (m-m/2-1, n%2==0?n/2-1:n/2);
return findMedianSortedArrays(A, m-num_abandom, B+num_abandom, n
-num_abandom);
}
}
};
【在 k*********6 的大作中提到】
: 我这道题写的程序好ugly啊。能请大牛们share一下漂亮点的解法吗？
|
|
