j**l
发帖数: 2911 | 1 A和B都是有序数组(可能有重复的数)，A的长度为m, B的长度为n, m和n不一定相等。要
求用
O(1)空间和log(m+n)时间求A和B归并(不删除重复的数)后的那个长度为m+n的有序数组
的median。奇数个有序数组的median为中间那个数，偶数个有序数组的median为中间那
两个数的平均数。 | s*****y
发帖数: 897 | 2 Is it the same as this one?
Find the k-th Smallest Element in the Union of Two Sorted Arrays
http://www.ihas1337code.com/2011/01/find-k-th-smallest-element-
You have length M and N sorted array. Just fine the M+N/2 smallers element.
【在 j**l 的大作中提到】
: A和B都是有序数组(可能有重复的数)，A的长度为m, B的长度为n, m和n不一定相等。要
: 求用
: O(1)空间和log(m+n)时间求A和B归并(不删除重复的数)后的那个长度为m+n的有序数组
: 的median。奇数个有序数组的median为中间那个数，偶数个有序数组的median为中间那
: 两个数的平均数。
| j*****u
发帖数: 1133 | 3 m==n的时候就是每次drop A和B的各一半吧
m!=n的时候可以每次drop min(m/2, n/2)?
【在 j**l 的大作中提到】
: A和B都是有序数组(可能有重复的数)，A的长度为m, B的长度为n, m和n不一定相等。要
: 求用
: O(1)空间和log(m+n)时间求A和B归并(不删除重复的数)后的那个长度为m+n的有序数组
: 的median。奇数个有序数组的median为中间那个数，偶数个有序数组的median为中间那
: 两个数的平均数。
| a***y
发帖数: 547 | 4 you can drop (m+n)/2 each time
【在 j*****u 的大作中提到】
: m==n的时候就是每次drop A和B的各一半吧
: m!=n的时候可以每次drop min(m/2, n/2)?
| i**********e
发帖数: 1145 | 5 The "Find k-th smallest element" can be applied directly when m+n is odd.
However, if m+n is even, you have to call the function twice and average the
two values to get the median.
A better way to do this is to get the median (X and Y) from the two arrays
and compare. If X < Y, then the real median of two sorted arrays must be
somewhere between X and Y. Similar for when X >= Y, then the real median
must be somewhere between Y and X.
For arrays of different size (ie: m != n), we must be careful when disposing
elements from the array. Each time we must dispose an equal amount of
elements. More specifically, we are disposing min(m,n) elements in each
iteration.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
.
【在 s*****y 的大作中提到】
: Is it the same as this one?
: Find the k-th Smallest Element in the Union of Two Sorted Arrays
: http://www.ihas1337code.com/2011/01/find-k-th-smallest-element-
: You have length M and N sorted array. Just fine the M+N/2 smallers element.
| i**********e
发帖数: 1145 | 6 贴一贴我的代码吧，抛砖引玉.
代码已经改了好几遍，尽量简洁，但是有一些部分还是非常 tricky 的.
代码经过严格的测试.
如果你要测试数据，可以站内联系我.
另外要提到的是:
我想这题难度系数还是满大的，网上的解法不一定对，例如这个就有好几个 bug:
http://geeksforgeeks.org/?p=2105
第一，没有得到平均和（他的直接除以二然后 truncate ）
第二，测试了有好几个 case 没通过
很多网上的答案都只能够处理 m == n 的情况，看来 m != n 的情况复杂很多，其实不
是. 掌握思路要点后一点也不难，就是要确保这个 invariant 得到满足:
-- 每次从数组 A 和数组 B 去掉的元素个数必须相等.
掌握了以上的每次去除元素的思路，递归就很直接可以写出来，这只是解这道题最简单
的部分，更难的还有以下非常 tricky 的要点：
1）怎么知道递归的终止条件？ 应该很容易想到当其中一个数组个数为 1 的时候，就
必须个别处理，不然就会死循环. 而为什么其中数组个数为 2 的时候也必须个别处理
就不是那么明显了.
2）当个别处理 special case 的时候，这是最 tricky 的部分，要考虑到很多不同的
情况，要非常谨慎. 我想，如果要使这代码更简洁的话，就是尽量把 special case 减
少，但是我还没想到有什么方法可以除掉这些繁琐的 special case.
// Prerequisite: a must be less than or equal to b
double medianOfThree(int a, int b, int val) {
assert(a <= b);
if (val <= a)
return a;
else if (val <= b)
return val;
else /* val > b */
return b;
}
double findMedianBaseCase(int med, int C[], int n) {
if (n == 1)
return (med+C[0])/2.0;
if (n % 2 == 0) {
int a = C[n/2 - 1], b = C[n/2];
return medianOfThree(a, b, med);
} else {
int a = C[n/2 - 1], b = C[n/2], c = C[n/2 + 1];
return (min(max(a,med), c) + b) / 2.0;
}
}
double findMedianBaseCase2(int med1, int med2, int C[], int n) {
if (n % 2 == 0) {
int a = C[n/2 - 1], b = C[n/2];
return (max(med1, a) + min(med2, b)) / 2.0;
} else {
int a = C[n/2 - 1], b = C[n/2], c = C[n/2 + 1];
return medianOfThree(min(med1, c), max(med2, a), b);
}
}
// Assumption: A and B are both sorted
double findMedian(int A[], int m, int B[], int n) {
assert(m > 0); assert(n > 0);
if (m == 1)
return findMedianBaseCase(A[0], B, n);
else if (n == 1)
return findMedianBaseCase(B[0], A, m);
else if (m == 2)
return findMedianBaseCase2(A[0], A[1], B, n);
else if (n == 2)
return findMedianBaseCase2(B[0], B[1], A, m);
int i = m/2, j = n/2;
if (A[i] <= B[j]) {
int k = min(i, n-j-1);
assert(k > 0);
return findMedian(A+k, m-k, B, n-k);
} else {
int k = min(m-i-1, j);
assert(k > 0);
return findMedian(A, m-k, B+k, n-k);
}
}
一些常见面试题的答案与总结 -
http://www.ihas1337code.com | a***y
发帖数: 117 | 7
hi, could you explain a little more on why we should discard the min(i, n-
j-1) or min(n-i-1,j) length of elements?
another question, inside of else statement of findMedianBaseCase2
function, how you figure out we should get min value between med1 and c
and get max value between med2 and a first ?
thank you.
【在 i**********e 的大作中提到】
: 贴一贴我的代码吧，抛砖引玉.
: 代码已经改了好几遍，尽量简洁，但是有一些部分还是非常 tricky 的.
: 代码经过严格的测试.
: 如果你要测试数据，可以站内联系我.
: 另外要提到的是:
: 我想这题难度系数还是满大的，网上的解法不一定对，例如这个就有好几个 bug:
: http://geeksforgeeks.org/?p=2105
: 第一，没有得到平均和（他的直接除以二然后 truncate ）
: 第二，测试了有好几个 case 没通过
: 很多网上的答案都只能够处理 m == n 的情况，看来 m != n 的情况复杂很多，其实不
| i**********e
发帖数: 1145 | 8 #1 This line of code :
return medianOfThree(min(med1, c), max(med2, a), b);
#2 is the result of refactoring the below (easier to understand):
if (med1 >= b)
return min(med1, c);
else if (med2 <= b)
return max(med2, a);
else /* med1 < b < med2 */
return b;
In real world, I would choose the latter because the logic is clearer. Could
you see why the #1 will always yield the same result as #2?
To answer your 2nd question, assume X = A[i] and Y = B[j], where i=m/2 and j
=n/2.
If (X <= Y), then you know that the median must be between X and Y.
Therefore we can dispose all elements before X in A and all element after Y
in B. But to maintain the balance and invariant, you must dispose equal
elements from A and B. (This is very important or your algo is incorrect).
Therefore we choose the minimum number of elements to dispose, which is k =
min(i, n-j-1).
By the way I saw this problem in CLRS book Chapter 9, they have a more
elegant solution, but it is for the special case where m == n == 2*N (even
number). Maybe we can extend this to support the general case where m != n.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 a***y 的大作中提到】
:
: hi, could you explain a little more on why we should discard the min(i, n-
: j-1) or min(n-i-1,j) length of elements?
: another question, inside of else statement of findMedianBaseCase2
: function, how you figure out we should get min value between med1 and c
: and get max value between med2 and a first ?
: thank you.
| s*****y
发帖数: 897 | 9 can you give me your input to test.
I extend your solution in finding kth smallest element without calling it
two times.
I test
1. {1} {2}
2. {1}, {2,3}
3, {1,2}, {3,4}
4 {1,2} {4,5,6}
#define MAX(A,B) ((A) > (B) ? (A):(B))
#define MIN(A,B) ((A) < (B) ? (A):(B))
static int A[] = {2};
static int B[] = {1};
/* Find the Kth smallest element of sorted array A and B */
double Find_Kth_Smallest(int A[], int len1, int B[], int len2, int k, bool
divide)
{
int i, j;
int Ai, Ai_1, Bj, Bj_1; /* Ai_1 is i+1 Bj_1 is J+1 */
/* Handle the special case */
if (len1+len2 < k)
return 0;
if (len1+len2 == k)
return MAX(A[len1-1], B[len2-1]);
if ((len1 == 1) && (len2 == 1) && divide)
return (double)(A[0] + B[0])/2;
if ((len1 == 1) && (len2 == 2) || ((len1 == 2) && (len2 == 1) ))
return MAX(A[0], B[0]);
/* keep i + j = k-1 */
i = len1*(k-1)/(len1+len2);
j = k- 1 - i;
Ai = A[i-1];
Ai_1 = A[i];
Bj = B[j-1];
Bj_1 = B[j];
if ((Ai < Bj_1) && ( Bj_1 < Ai_1)) {
if (divide) {
return double(Bj_1 + MIN(Ai_1, B[j+1]))/2;
} else {
return Bj_1;
}
}
if ((Bj < Ai_1) && ( Ai_1< Bj_1)) {
if (divide) {
return double(Ai_1 + MIN(A[i+1], Bj_1))/2;
} else {
return Ai_1;
}
}
if (Bj_1 > Ai_1) {
/* Drop the element j in B array */
return Find_Kth_Smallest(A+i, len1-i, B, j, k-i, divide);
}
if (Bj_1 < Ai_1) {
/* Drop the element >i in A and
return Find_Kth_Smallest(A, len1, B+j, j, k-j, divide);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int size_A = sizeof(A)/sizeof(int);
int size_B = sizeof(B)/sizeof(int);
int median_index;
/* use the double to return the media value */
double median;
/* check whether we need to divide the media value */
bool divide = ((size_A + size_B)%2 == 0)? 1:0;
if (divide)
/* average the median_index and median_index+1 */
median_index = (size_A + size_B) / 2;
else
median_index = (size_A + size_B + 1) / 2;
median = Find_Kth_Smallest(A, size_A, B, size_B, median_index, divide);
return 0;
}
【在 i**********e 的大作中提到】
: 贴一贴我的代码吧，抛砖引玉.
: 代码已经改了好几遍，尽量简洁，但是有一些部分还是非常 tricky 的.
: 代码经过严格的测试.
: 如果你要测试数据，可以站内联系我.
: 另外要提到的是:
: 我想这题难度系数还是满大的，网上的解法不一定对，例如这个就有好几个 bug:
: http://geeksforgeeks.org/?p=2105
: 第一，没有得到平均和（他的直接除以二然后 truncate ）
: 第二，测试了有好几个 case 没通过
: 很多网上的答案都只能够处理 m == n 的情况，看来 m != n 的情况复杂很多，其实不
| i**********e
发帖数: 1145 | 10 A = { 3 }
B = { 1 2 }
Your answer: 3
Expected: 2
A = { 1 3 4 }
B = { 2 }
Your answer: Infinite loop
Expected: 2.5
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 s*****y 的大作中提到】
: can you give me your input to test.
: I extend your solution in finding kth smallest element without calling it
: two times.
: I test
: 1. {1} {2}
: 2. {1}, {2,3}
: 3, {1,2}, {3,4}
: 4 {1,2} {4,5,6}
: #define MAX(A,B) ((A) > (B) ? (A):(B))
: #define MIN(A,B) ((A) < (B) ? (A):(B))
| i**********e
发帖数: 1145 | 11 MIT 的 handout 里有提出这题的解答，利用 binary search 巧妙的思路.
http://www2.myoops.org/course_material/mit/NR/rdonlyres/Electri
但是我觉得他那里指的 median 定义似乎不完全对:
Suppose that the median is A[i]. Since the array is sorted, it is greater
than exactly i−1 values in array A. Then if it is the median, it is
also greater than exactly j = ceiling(n/2) − (i − 1) elements in
B.
根据以上的定义，两个数组总数 (n) 为偶数时，取的 median 是元素第 n/2 个，而不
是两个相邻元素之平均. 不知道有没有理解错误，请高人指引.
觉得主要难度要找寻当数组总数为偶数时，要找到两个相邻的元素再找平均. 如果要找
一个元素就容易，但是似乎同时间找两个相邻的元素似乎比较繁琐. （或者先找到第一
个元素，再找与它相邻的元素？这样那个 invariant 似乎又要复杂不少).
一些常见面试题的答案与总结 -
http://www.ihas1337code.com | i**********e
发帖数: 1145 | 12 最近刚制造了更多的 test cases，发现我的代码出现了两个 bug.
大家当作练习找找看吧...
五个小时后公布答案
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
