H*M
发帖数: 1268 | 1 其实远比你们想象的要纷繁复杂.别以为每次甩掉一半就好了.
写下code try try呵呵.如果你能在半小时之内编好没bug(真实性全凭自觉),我2个包子
送上.嘿嘿. |
y****i
发帖数: 23 | 2 没给任何限制，那就多用m+n的空间，把A，B合成一个array O(m+n), 取median O(1) |
g*******y
发帖数: 1930 | 3 如果一个数组个数为偶数，median的定义是中间两个数，还是其平均值？ |
S*********N
发帖数: 6151 | 4
这位同学做题做疯了？
我觉得的你的水平比我高很多。
人际关系和运气很重要。不要限于题海战术。
【在 H*M 的大作中提到】
: 其实远比你们想象的要纷繁复杂.别以为每次甩掉一半就好了.
: 写下code try try呵呵.如果你能在半小时之内编好没bug(真实性全凭自觉),我2个包子
: 送上.嘿嘿.
|
H*M
发帖数: 1268 | 5 median定义为:
如果是奇数,则是中间的那个数
如果是偶数,则为中间两个数的平均.
【在 g*******y 的大作中提到】
: 如果一个数组个数为偶数，median的定义是中间两个数，还是其平均值？
|
E*******0
发帖数: 465 | |
H*M
发帖数: 1268 | 7 我当然知道log(m+n)
我说的是知道怎么做,但是写不出正确的code短时间里
是很多人的通病
【在 E*******0 的大作中提到】
: log(m+n)
|
E*******0
发帖数: 465 | 8 length(A)=n; length(B)=m.
Get the median of array A, get the kth in array B.
if k
if k=m/m;
if k>m/2;
Answer question for the RP. |
E*******0
发帖数: 465 | 9 rs=function(A,aS,aE,B,bS,bE)
{
n=length(A);
m=length(B);
flag=A((aS+aE)/2);
k=pos(B,flag);
if ((aS+aE)/2+k)==(m+n)/2)
bid it;
elseif ((aS+aE)/2+k)<(m+n)/2)
elseif ((aS+aE)/2+k)<(m+n)/2)
} |
E*******0
发帖数: 465 | 10 recursive function.
It cost too much time.
hehe. Just idea, hehe. |
|
|
H*M
发帖数: 1268 | 11 我说的是可以执行的没有bug的code
【在 E*******0 的大作中提到】
: rs=function(A,aS,aE,B,bS,bE)
: {
: n=length(A);
: m=length(B);
: flag=A((aS+aE)/2);
: k=pos(B,flag);
: if ((aS+aE)/2+k)==(m+n)/2)
: bid it;
: elseif ((aS+aE)/2+k)<(m+n)/2)
: elseif ((aS+aE)/2+k)<(m+n)/2)
|
E*******0
发帖数: 465 | 12 Sorry. my answer is wrong. My LD gave me a better answer which time
complexity is log(m+n). |
j*****j
发帖数: 115 | 13 int foo(int* a, int* b, int a_min, int a_max, int b_min, int b_max)
{
if((a_max-a_min==1)&&(b_max-b_min==1)) return median of a[a_min],a[a_max
],b[b_min],b[b_max];
int a_mid=(a_min+a_max)/2;
int b_mid=ceil((b_min+b_max)/2);
if(a[a_mid]==b[b_mid]) return a[a_mid];
elseif(a[a_mid]
else return foo(a,b,a_min,a_mid,b_mid,b_max);
} |
H*M
发帖数: 1268 | 14 sommthing like this wont be good
max
【在 j*****j 的大作中提到】
: int foo(int* a, int* b, int a_min, int a_max, int b_min, int b_max)
: {
: if((a_max-a_min==1)&&(b_max-b_min==1)) return median of a[a_min],a[a_max
: ],b[b_min],b[b_max];
:
: int a_mid=(a_min+a_max)/2;
: int b_mid=ceil((b_min+b_max)/2);
: if(a[a_mid]==b[b_mid]) return a[a_mid];
: elseif(a[a_mid]: else return foo(a,b,a_min,a_mid,b_mid,b_max);
|
j*****j
发帖数: 115 | 15 这个代码有什么问题吗？
我觉得这道题目在coding的时候有两个地方比较tricks
第一个是recurvise的结束条件，是剩4个元素的时候结束。
第二个是ceil()来找第二个数组的median，主要是保证数组是偶数个时，两边扔掉的数
组个数一样 |
H*M
发帖数: 1268 | 16 I dont have time to check your codes..
Write bug free codes and I will send you the test cases.
【在 j*****j 的大作中提到】
: 这个代码有什么问题吗？
: 我觉得这道题目在coding的时候有两个地方比较tricks
: 第一个是recurvise的结束条件，是剩4个元素的时候结束。
: 第二个是ceil()来找第二个数组的median，主要是保证数组是偶数个时，两边扔掉的数
: 组个数一样
|
l******o
发帖数: 144 | 17 能给我发一份test cases么? 想测试一下看对不对. 多谢,呵呵. 当然花了不止30分钟
就是了.
I dont have time to check your codes..
Write bug free codes and I will send you the test cases.
【在 H*M 的大作中提到】
: I dont have time to check your codes..
: Write bug free codes and I will send you the test cases.
|
n**x
发帖数: 30 | 18 写得有点恶心，细节没有优化。后半部分感觉可以优化掉，但不知道怎么证明。
#include
#include
inline int IsOdd(int x){
return (x&1)==1;
}
inline int IsEven(int x){
return (x&1)==0;
}
int getmedian(int *s1,int *e1,int *s2,int *e2){
int N1=(e1-s1),N2=(e2-s2);
int N=N1+N2;
int NHalf=(N1+N2)>>1;
float m1,m2;
int remainHead=0,remainTail=0;
while(remainHead
N1=(e1-s1);
N2=(e2-s2);
if(IsOdd(N1)) m1=s1[N1>>1];
else m1=(s1[(N1>>1)-1]+
【在 H*M 的大作中提到】
: 其实远比你们想象的要纷繁复杂.别以为每次甩掉一半就好了.
: 写下code try try呵呵.如果你能在半小时之内编好没bug(真实性全凭自觉),我2个包子
: 送上.嘿嘿.
|
b****j
发帖数: 78 | 19 这道题是log(m+n)吗？我觉得只能做到log(m*n)
【在 E*******0 的大作中提到】
: Sorry. my answer is wrong. My LD gave me a better answer which time
: complexity is log(m+n).
|
r*****t
发帖数: 712 | 20 两个数组大小，然后数数不就好了吗？
【在 H*M 的大作中提到】
: 其实远比你们想象的要纷繁复杂.别以为每次甩掉一半就好了.
: 写下code try try呵呵.如果你能在半小时之内编好没bug(真实性全凭自觉),我2个包子
: 送上.嘿嘿.
|
x***y
发帖数: 633 | 21 Can you give some details about the algorithm when m!=n? thanks..
【在 H*M 的大作中提到】
: 我当然知道log(m+n)
: 我说的是知道怎么做,但是写不出正确的code短时间里
: 是很多人的通病
|
