请帖个Median of Two Sorted Arrays的好解法？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

请帖个Median of Two Sorted Arrays的好解法？

请帖个Median of Two Sorted Arrays的好解法？# JobHunting - 待字闺中

y*o2013-10-12 07:10

1 楼

很多人把骗子的id地址等记录下来。其实那些没用，骗子也不care那些。因为都是假的。
但是那些evil buyer就不一样了。那些动不动就刷赖的，都是真人，就是那些非常mean
的真人，
有人可以和我联系一下。我目前只联系麦美国产的电子（在美国商店进的货）其他中国
产的或服装，绒毛玩具之类的就算了。

b*t2013-10-12 07:10

2 楼

【以下文字转载自 WaterWorld 讨论区】
发信人: bkht (bkht), 信区: WaterWorld
标题: 看了social network后，觉得白男对wf亚女评价很差呀！
发信站: BBS 未名空间站 (Sat Dec 25 14:06:37 2010, 美东)
开始几个白男讨论为什么亚女那么喜欢犯贱倒贴，急不可耐的到厕所suck their dicks
。后来一个亚女发现她白男bf在facebook上还是单身，醋意大发，歇斯底里。结果被甩
后，又贱兮兮的后悔求饶。那个白男对她的评价就是bitchy and bossy。
真是可悲呀！
看来wf女孩要努力提高自身修养，光靠犯贱suck dick是不行的，精神上也要成为奴隶
才行。

k*62013-10-12 07:10

3 楼

我这道题写的程序好ugly啊。能请大牛们share一下漂亮点的解法吗？

m*i2013-10-12 07:10

4 楼

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*62013-10-12 07:10

5 楼

赞，比俺自己写的强100倍不止。

r*n2013-10-12 07:10

6 楼

收藏了

【在 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*n2013-10-12 07:10

7 楼

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 (valelse 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一下漂亮点的解法吗？