K*****k
发帖数: 430 | 1 要求in place, 只要求O(m + n)的方法，不需要log(m + n)那个。我写的代码还是觉得太长，怎么简化才能在白板上写的下？
double GetMedian(int A[], int m, int B[], int n)
{
bool odd_length = ((m + n) % 2 == 0)? false : true;
int m1, m2;
int pos = (m + n + 1) / 2;
int count = 0;
int i = 0;
int j = 0;
while (i < m && j < n)
{
count++;
if (A[i] <= B[j])
{
if (count == pos)
{
m1 = A[i];
if (odd_length)
return m1;
}
else if (count == pos + 1)
{
m2 = A[i];
return (m1 + m2) / 2.0;
}
i++;
}
else
{
if (count == pos)
{
m1 = B[j];
if (odd_length)
return m1;
}
else if (count == pos + 1)
{
m2 = B[j];
return (m1 + m2) / 2.0;
}
j++;
}
}
while (i < m)
{
count++;
if (count == pos)
{
m1 = A[i];
if (odd_length)
return m1;
}
else if (count == pos + 1)
{
m2 = A[i];
return (m1 + m2) / 2.0;
}
i++;
}
while (j < n)
{
count++;
if (count == pos)
{
m1 = B[j];
if (odd_length)
return m1;
}
else if (count == pos + 1)
{
m2 = B[j];
return (m1 + m2) / 2.0;
}
j++;
}
return 0.0;
} | f*******t
发帖数: 7549 | 2 int median(int a[], int m, int b[], int n)
{
int target = (m + n) / 2; // Be careful for overflow
int indexA = 0, indexB = 0;
while(--target) {
if(indexA == m-1)
indexB++;
else if(indexB == n-1)
indexA++;
else if(a[indexA] < b[indexB])
indexA++;
else
indexB++;
}
if((m ^ n) & 1)
return min(a[indexA], b[indexB]);
else
return (a[indexA] + b[indexB]) / 2;
} | K*****k
发帖数: 430 | 3 没看明白。
而且当总共的元素个数为偶数的时候，median的定义是中间两个数的平均数。
比如
int A[] = {1};
int B[] = {5, 6, 7, 8, 9};
合并后是{1, 5, 6, 7, 8, 9}, median = (6 + 7) / 2 = 6.5
【在 f*******t 的大作中提到】
: int median(int a[], int m, int b[], int n)
: {
: int target = (m + n) / 2; // Be careful for overflow
: int indexA = 0, indexB = 0;
: while(--target) {
: if(indexA == m-1)
: indexB++;
: else if(indexB == n-1)
: indexA++;
: else if(a[indexA] < b[indexB])
| K*****k
发帖数: 430 | 4 这道题在ihasleetcode的网站上有巧妙的log(m+n)的解法，但对面试来说太难。
有人onsite的时候被问过这题么？ | f*******t
发帖数: 7549 | 5 要返回平均数的话改下最后的return语句就行。
最好的算法是logk的（找第k小的元素），其实不算难，我觉得面试考这题的机会还是挺多的，背好代
码就行。。。
【在 K*****k 的大作中提到】
: 没看明白。
: 而且当总共的元素个数为偶数的时候，median的定义是中间两个数的平均数。
: 比如
: int A[] = {1};
: int B[] = {5, 6, 7, 8, 9};
: 合并后是{1, 5, 6, 7, 8, 9}, median = (6 + 7) / 2 = 6.5
| K*****k
发帖数: 430 | 6 你原来的代码对test case
A[] = {1};
B[] = {5, 6, 7, 8, 9};
m = 1
n = 5
结果不对，好像return的时候去引用A[1], 越界了。能否检查一下。
是挺多的，背好代
【在 f*******t 的大作中提到】
: 要返回平均数的话改下最后的return语句就行。
: 最好的算法是logk的（找第k小的元素），其实不算难，我觉得面试考这题的机会还是挺多的，背好代
: 码就行。。。
| k****n
发帖数: 369 | 7 我被问过，当时就毛了，最后歇比了
算法上根本没啥难的，各种小细节小边界条件，坑死爹阿
以后见到老印就拿这个问，定了
【在 K*****k 的大作中提到】
: 这道题在ihasleetcode的网站上有巧妙的log(m+n)的解法，但对面试来说太难。
: 有人onsite的时候被问过这题么？
| f*******t
发帖数: 7549 | 8 嗯，确实有bug
在原楼编辑了
【在 K*****k 的大作中提到】
: 你原来的代码对test case
: A[] = {1};
: B[] = {5, 6, 7, 8, 9};
: m = 1
: n = 5
: 结果不对，好像return的时候去引用A[1], 越界了。能否检查一下。
:
: 是挺多的，背好代
| B*******1
发帖数: 2454 | 9 1337那个帖子下面有个读者给出的也是最优化的，1337也肯定了那个人的code，而且写
得很简单，就是改mit的解法出来的。
1337那个写得太复杂了。
【在 k****n 的大作中提到】
: 我被问过，当时就毛了，最后歇比了
: 算法上根本没啥难的，各种小细节小边界条件，坑死爹阿
: 以后见到老印就拿这个问，定了
| K*****k
发帖数: 430 | 10 那个log(m + n)的算法现场想到还是很难的，好像MIT某个课程的handout中有解答，但
对偶数个元素，也是求出第一个median, 而不是两个median的平均值。
ihasleetcode的网站有完整巧妙的几种解答方法，可惜我觉得对于面试的白板来说，可
用空间太小了，写不下。
【在 k****n 的大作中提到】
: 我被问过，当时就毛了，最后歇比了
: 算法上根本没啥难的，各种小细节小边界条件，坑死爹阿
: 以后见到老印就拿这个问，定了
| | | H*M
发帖数: 1268 | 11 跟merge sort比较象，往前爬，同事记住爬的数目，等总共爬了一半，就是中树的附近
？不过边界条件要整一整
得太长，怎么简化才能在白板上写的下？
【在 K*****k 的大作中提到】
: 要求in place, 只要求O(m + n)的方法，不需要log(m + n)那个。我写的代码还是觉得太长，怎么简化才能在白板上写的下？
: double GetMedian(int A[], int m, int B[], int n)
: {
: bool odd_length = ((m + n) % 2 == 0)? false : true;
: int m1, m2;
: int pos = (m + n + 1) / 2;
: int count = 0;
: int i = 0;
: int j = 0;
: while (i < m && j < n)
| f*******t
发帖数: 7549 | 12 lgk查找递归方法不长的，我顺便发个收藏的代码吧。记不得作者是谁……
int findKthFrom2SortedArraysIterative(int *arr1, int *arr2, int k){
int result;
int mid;
int curPosOfArr1 = 0, curPosOfArr2 = 0;
while(k > 1){
mid = k/2;
if(arr1[curPosOfArr1 + mid - 1] < arr2[curPosOfArr2 + mid - 1]){
curPosOfArr1 = curPosOfArr1 + mid;
}else{
curPosOfArr2 = curPosOfArr2 + mid;
}
k = k - mid;
}
if(arr1[curPosOfArr1] > arr2[curPosOfArr2]){
return arr2[curPosOfArr2];
}else{
return arr1[curPosOfArr1];
}
return result;
}
int findKthFrom2SortedArraysRecursion(int *arr1, int *arr2, int k, int
arr1Index, int arr2Index){
if(k == 1){
if(arr1[arr1Index] <= arr2[arr2Index])
return arr1[arr1Index];
else
return arr2[arr2Index];
}
int curPos = k/2;
if(arr1[arr1Index + curPos - 1] <= arr2[arr2Index + curPos - 1])
findKthFrom2SortedArraysRecursion(arr1, arr2, k - curPos, arr1Index
+ curPos, arr2Index);
else
findKthFrom2SortedArraysRecursion(arr1, arr2, k - curPos, arr1Index,
arr2Index + curPos);
} | b******g
发帖数: 1721 | 13 大概的还不错。
A[] = {1};
B[] = {5, 6, 7, 8, 9};
m = 1
n = 5
用楼上的例子，你的算法要越界啊，是针对第一个数组arr1在第二次循环的时候。
【在 f*******t 的大作中提到】
: lgk查找递归方法不长的，我顺便发个收藏的代码吧。记不得作者是谁……
: int findKthFrom2SortedArraysIterative(int *arr1, int *arr2, int k){
: int result;
: int mid;
: int curPosOfArr1 = 0, curPosOfArr2 = 0;
: while(k > 1){
: mid = k/2;
: if(arr1[curPosOfArr1 + mid - 1] < arr2[curPosOfArr2 + mid - 1]){
:
: curPosOfArr1 = curPosOfArr1 + mid;
| b******g
发帖数: 1721 | 14 这个挺好的，不过
最后(m ^ n) & 1 能不能改成 (m==n)啊，要不然太耍深奥了吧。
【在 f*******t 的大作中提到】
: int median(int a[], int m, int b[], int n)
: {
: int target = (m + n) / 2; // Be careful for overflow
: int indexA = 0, indexB = 0;
: while(--target) {
: if(indexA == m-1)
: indexB++;
: else if(indexB == n-1)
: indexA++;
: else if(a[indexA] < b[indexB])
| A**u
发帖数: 2458 | 15 这玩意太复杂了
得太长，怎么简化才能在白板上写的下？
【在 K*****k 的大作中提到】
: 要求in place, 只要求O(m + n)的方法，不需要log(m + n)那个。我写的代码还是觉得太长，怎么简化才能在白板上写的下？
: double GetMedian(int A[], int m, int B[], int n)
: {
: bool odd_length = ((m + n) % 2 == 0)? false : true;
: int m1, m2;
: int pos = (m + n + 1) / 2;
: int count = 0;
: int i = 0;
: int j = 0;
: while (i < m && j < n)
| f*******t
发帖数: 7549 | 16 这句是用来判断m+n的奇偶性……
【在 b******g 的大作中提到】
: 这个挺好的，不过
: 最后(m ^ n) & 1 能不能改成 (m==n)啊，要不然太耍深奥了吧。
| w********p
发帖数: 948 | 17 请教您指的ihasleetcode是http://www.leetcode.com/ 还是http://www.weiming.info/author/ihasleetcode/ 或是其他？
谢谢。
有包子送的哦！
【在 K*****k 的大作中提到】
: 这道题在ihasleetcode的网站上有巧妙的log(m+n)的解法，但对面试来说太难。
: 有人onsite的时候被问过这题么？
| C***U
发帖数: 2406 | 18 如果是m+n的话，只要用merge那样做就可以了吧。
得太长，怎么简化才能在白板上写的下？
【在 K*****k 的大作中提到】
: 要求in place, 只要求O(m + n)的方法，不需要log(m + n)那个。我写的代码还是觉得太长，怎么简化才能在白板上写的下？
: double GetMedian(int A[], int m, int B[], int n)
: {
: bool odd_length = ((m + n) % 2 == 0)? false : true;
: int m1, m2;
: int pos = (m + n + 1) / 2;
: int count = 0;
: int i = 0;
: int j = 0;
: while (i < m && j < n)
| x*******7
发帖数: 223 | 19 到底怎么答好呢？leetcode上面找中位数和找kth解法好像不一样吧。 | k*******p
发帖数: 219 | | e********e
发帖数: 12 | 21 用merge的方法写了下。
template
T findKthOf2SortedArray1(T P[], int s, T Q[], int t, int k)
{
// assume: 1 <= k <= (s+t)
int i=0, j=0;
for (int l = 0; l < k; l++){
if (i == s) j++;
else if (j == t) i++;
else {
if (P[i] < Q[j]) i++;
else j++;
}
}
if (i == 0) return Q[j-1];
else if (j == 0) return P[i-1];
else return max(P[i-1], Q[j-1]);
}
template
T medianOfTwoSortedArray3(T P[], int s, T Q[], int t)
{
int k = (s + t)/2;
if ( (s+t)%2 == 1 ) return findKthOf2SortedArray1(P,s,Q,t,k+1);
else {
T res1 = findKthOf2SortedArray1(P,s,Q,t,k);
T res2 = findKthOf2SortedArray1(P,s,Q,t,k+1);
return (res1+res2)/2;
}
}
【在 C***U 的大作中提到】
: 如果是m+n的话，只要用merge那样做就可以了吧。
:
: 得太长，怎么简化才能在白板上写的下？
| p*g
发帖数: 141 | 22 可惜没有越界检查
这个代码还是不对
【在 f*******t 的大作中提到】
: lgk查找递归方法不长的，我顺便发个收藏的代码吧。记不得作者是谁……
: int findKthFrom2SortedArraysIterative(int *arr1, int *arr2, int k){
: int result;
: int mid;
: int curPosOfArr1 = 0, curPosOfArr2 = 0;
: while(k > 1){
: mid = k/2;
: if(arr1[curPosOfArr1 + mid - 1] < arr2[curPosOfArr2 + mid - 1]){
:
: curPosOfArr1 = curPosOfArr1 + mid;
|
|
