C***U 发帖数: 2406 | 1 我把leetcode上好多例子拿到机器上测试了 都没出错
但是在leetcode上会time limit exceeded
应该是有一个死循环
我找不出来
double findMedian(int A[], int m, int B[], int n) {
if(!n) {
return (A[(m - 1)/ 2] + A[(m - 1)/ 2 + (m - 1) % 2]) / 2.0;
}
int aStart = -1, aEnd = (m + n - 1) / 2 - 1;
int bStart = -1, bEnd = 0;
while(true) {
if(bEnd + 1 < n && A[aEnd] <= B[bEnd + 1] && B[bEnd] <= A[aEnd + 1])
{
break;
}
if(bEnd == n - 1 && B[bEnd] <= A[aEnd + 1]) {
break;
}
if(A[aEnd] < B[bEnd]) {
aStart = aEnd;
aEnd = aEnd + (bEnd - bStart + 1) / 2;
bEnd = bEnd - (bEnd - bStart + 1) / 2;
}
else if(A[aEnd] == B[bEnd]) {
break;
}
else {
bStart = bEnd;
if(bEnd + (aEnd - aStart + 1) / 2 < n) {
bEnd = bEnd + (aEnd - aStart + 1) / 2;
aEnd = aEnd - (aEnd - aStart + 1) / 2;
}
else {
aEnd = aEnd - (n - 1 - bEnd);
bEnd = n - 1;
}
}
}
if((m + n) % 2) {
return A[aEnd] > B[bEnd] ? A[aEnd] : B[bEnd];
}
else {
if(aEnd == -1) {
return (B[n - 1] + A[0]) / 2.0;
}
if(bEnd == -1) {
return aEnd == m - 1 ? (A[m - 1] + B[0]) / 2.0 : (A[aEnd] + A[
aEnd + 1]) / 2.0;
}
if(bEnd == n - 1){
return (A[aEnd] + (A[aEnd + 1] > B[bEnd] ? A[aEnd + 1] : B[bEnd]
)) / 2.0;
}
return ((A[aEnd] > B[bEnd] ? A[aEnd] : B[bEnd]) + (A[aEnd + 1] < B[
bEnd + 1] ? A[aEnd + 1] : B[bEnd + 1])) / 2.0;
}
}
double findMedianSortedArrays(int A[], int m, int B[], int n) {
if(m >= n) {
return findMedian(A, m, B, n);
}
else {
return findMedian(B, n, A, m);
}
} | w****x 发帖数: 2483 | | C***U 发帖数: 2406 | 3 恩 刚才检查了半个小时 通过测试 总算把错误找出来了
这题目面试如果要写 必挂无疑啊!
【在 w****x 的大作中提到】 : 这题skip掉吧
| p*****2 发帖数: 21240 | | C***U 发帖数: 2406 | 5 我用c++的 不过你看我的code写的很难看。。。。
【在 p*****2 的大作中提到】 : 这题太难。C还要好写一些。Java不容易。
| p*****2 发帖数: 21240 | 6
C++应该能写的更简洁。
【在 C***U 的大作中提到】 : 我用c++的 不过你看我的code写的很难看。。。。
| C***U 发帖数: 2406 | 7 恩 我是初学者
所以还没有经验
希望能指点我一二
【在 p*****2 的大作中提到】 : : C++应该能写的更简洁。
| p*****2 发帖数: 21240 | 8
我C++不懂,问上边的大牛吧。我上次用Java写的惨不忍睹呀。
【在 C***U 的大作中提到】 : 恩 我是初学者 : 所以还没有经验 : 希望能指点我一二
| B*******1 发帖数: 2454 | 9 My code, pass all the test.
double findKth(int a[], int m, int b[], int n, int k)
{
if (m > n) return findKth(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), pb = k - pa;
if (a[pa-1] < b[pb-1]) return findKth(a+pa, m-pa, b, n, k - pa);
return findKth(a, m, b+pb, n-pb, k-pb);
}
class Solution {
public:
double findMedianSortedArrays(int A[], int m, int B[], int n) {
int total = m+n;
if (total&0x1)
return findKth(A, m, B, n, total/2+1);
else
return (findKth(A, m, B, n, total/2) + findKth(A, m, B, n, total/2+1
))/2;
}
};
【在 C***U 的大作中提到】 : 我把leetcode上好多例子拿到机器上测试了 都没出错 : 但是在leetcode上会time limit exceeded : 应该是有一个死循环 : 我找不出来 : double findMedian(int A[], int m, int B[], int n) { : if(!n) { : return (A[(m - 1)/ 2] + A[(m - 1)/ 2 + (m - 1) % 2]) / 2.0; : } : int aStart = -1, aEnd = (m + n - 1) / 2 - 1; : int bStart = -1, bEnd = 0;
| p*****2 发帖数: 21240 | 10
貌似玄铁的算法?
【在 B*******1 的大作中提到】 : My code, pass all the test. : double findKth(int a[], int m, int b[], int n, int k) : { : if (m > n) return findKth(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), pb = k - pa; : if (a[pa-1] < b[pb-1]) return findKth(a+pa, m-pa, b, n, k - pa); : return findKth(a, m, b+pb, n-pb, k-pb); : }
| | | B*******1 发帖数: 2454 | 11 是啊,学习大牛得。
【在 p*****2 的大作中提到】 : : 貌似玄铁的算法?
| C***U 发帖数: 2406 | 12 恩 用递归不错 果然好写好多
膜拜你
不过我最近想练习尽量不用递归。。。
【在 B*******1 的大作中提到】 : My code, pass all the test. : double findKth(int a[], int m, int b[], int n, int k) : { : if (m > n) return findKth(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), pb = k - pa; : if (a[pa-1] < b[pb-1]) return findKth(a+pa, m-pa, b, n, k - pa); : return findKth(a, m, b+pb, n-pb, k-pb); : }
| p*****2 发帖数: 21240 | 13
牛逼呀。膜拜一下。
【在 B*******1 的大作中提到】 : 是啊,学习大牛得。
| C***U 发帖数: 2406 | 14 我做leetcode前一半用递归。。。然后被我同学鄙视了
后一半我就不用递归了。。。嘎嘎
【在 p*****2 的大作中提到】 : : 牛逼呀。膜拜一下。
| p*****2 发帖数: 21240 | 15
不要死较真。看题。这题写成这样已经很牛逼了。我同样的算法用Java写,难写很多。
因为没有指针的灵活性。
【在 C***U 的大作中提到】 : 恩 用递归不错 果然好写好多 : 膜拜你 : 不过我最近想练习尽量不用递归。。。
| w****x 发帖数: 2483 | 16 对阿, median of 2 sorted array 就是kth element of two sorted array的变体,
后者简洁多了, 但是收敛速度不一样啊 | C***U 发帖数: 2406 | 17 好 明白了
哈哈哈
他写的code确实很牛 那么短!
【在 p*****2 的大作中提到】 : : 不要死较真。看题。这题写成这样已经很牛逼了。我同样的算法用Java写,难写很多。 : 因为没有指针的灵活性。
| D****3 发帖数: 611 | 18 这题leetcode有问题,我直接打public class Solution {
public double findMedianSortedArrays(int A[], int B[]) {
return 0;
}
}
他说我超时。。。他扯淡吧 | p*****2 发帖数: 21240 | 19
总是这样吗?有的时候人多会这样。
【在 D****3 的大作中提到】 : 这题leetcode有问题,我直接打public class Solution { : public double findMedianSortedArrays(int A[], int B[]) { : return 0; : } : } : 他说我超时。。。他扯淡吧
| C***U 发帖数: 2406 | 20 那应该是人品问题 哈哈哈
有时候他可能在维护什么的吧?
【在 D****3 的大作中提到】 : 这题leetcode有问题,我直接打public class Solution { : public double findMedianSortedArrays(int A[], int B[]) { : return 0; : } : } : 他说我超时。。。他扯淡吧
| | | e***s 发帖数: 799 | 21 LeetCode上这题的OJ很奇怪,O(n)居然能过Large case | C***U 发帖数: 2406 | 22 我把leetcode上好多例子拿到机器上测试了 都没出错
但是在leetcode上会time limit exceeded
应该是有一个死循环
我找不出来
double findMedian(int A[], int m, int B[], int n) {
if(!n) {
return (A[(m - 1)/ 2] + A[(m - 1)/ 2 + (m - 1) % 2]) / 2.0;
}
int aStart = -1, aEnd = (m + n - 1) / 2 - 1;
int bStart = -1, bEnd = 0;
while(true) {
if(bEnd + 1 < n && A[aEnd] <= B[bEnd + 1] && B[bEnd] <= A[aEnd + 1])
{
break;
}
if(bEnd == n - 1 && B[bEnd] <= A[aEnd + 1]) {
break;
}
if(A[aEnd] < B[bEnd]) {
aStart = aEnd;
aEnd = aEnd + (bEnd - bStart + 1) / 2;
bEnd = bEnd - (bEnd - bStart + 1) / 2;
}
else if(A[aEnd] == B[bEnd]) {
break;
}
else {
bStart = bEnd;
if(bEnd + (aEnd - aStart + 1) / 2 < n) {
bEnd = bEnd + (aEnd - aStart + 1) / 2;
aEnd = aEnd - (aEnd - aStart + 1) / 2;
}
else {
aEnd = aEnd - (n - 1 - bEnd);
bEnd = n - 1;
}
}
}
if((m + n) % 2) {
return A[aEnd] > B[bEnd] ? A[aEnd] : B[bEnd];
}
else {
if(aEnd == -1) {
return (B[n - 1] + A[0]) / 2.0;
}
if(bEnd == -1) {
return aEnd == m - 1 ? (A[m - 1] + B[0]) / 2.0 : (A[aEnd] + A[
aEnd + 1]) / 2.0;
}
if(bEnd == n - 1){
return (A[aEnd] + (A[aEnd + 1] > B[bEnd] ? A[aEnd + 1] : B[bEnd]
)) / 2.0;
}
return ((A[aEnd] > B[bEnd] ? A[aEnd] : B[bEnd]) + (A[aEnd + 1] < B[
bEnd + 1] ? A[aEnd + 1] : B[bEnd + 1])) / 2.0;
}
}
double findMedianSortedArrays(int A[], int m, int B[], int n) {
if(m >= n) {
return findMedian(A, m, B, n);
}
else {
return findMedian(B, n, A, m);
}
} | w****x 发帖数: 2483 | | C***U 发帖数: 2406 | 24 恩 刚才检查了半个小时 通过测试 总算把错误找出来了
这题目面试如果要写 必挂无疑啊!
【在 w****x 的大作中提到】 : 这题skip掉吧
| p*****2 发帖数: 21240 | | C***U 发帖数: 2406 | 26 我用c++的 不过你看我的code写的很难看。。。。
【在 p*****2 的大作中提到】 : 这题太难。C还要好写一些。Java不容易。
| p*****2 发帖数: 21240 | 27
C++应该能写的更简洁。
【在 C***U 的大作中提到】 : 我用c++的 不过你看我的code写的很难看。。。。
| C***U 发帖数: 2406 | 28 恩 我是初学者
所以还没有经验
希望能指点我一二
【在 p*****2 的大作中提到】 : : C++应该能写的更简洁。
| p*****2 发帖数: 21240 | 29
我C++不懂,问上边的大牛吧。我上次用Java写的惨不忍睹呀。
【在 C***U 的大作中提到】 : 恩 我是初学者 : 所以还没有经验 : 希望能指点我一二
| B*******1 发帖数: 2454 | 30 My code, pass all the test.
double findKth(int a[], int m, int b[], int n, int k)
{
if (m > n) return findKth(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), pb = k - pa;
if (a[pa-1] < b[pb-1]) return findKth(a+pa, m-pa, b, n, k - pa);
return findKth(a, m, b+pb, n-pb, k-pb);
}
class Solution {
public:
double findMedianSortedArrays(int A[], int m, int B[], int n) {
int total = m+n;
if (total&0x1)
return findKth(A, m, B, n, total/2+1);
else
return (findKth(A, m, B, n, total/2) + findKth(A, m, B, n, total/2+1
))/2;
}
};
【在 C***U 的大作中提到】 : 我把leetcode上好多例子拿到机器上测试了 都没出错 : 但是在leetcode上会time limit exceeded : 应该是有一个死循环 : 我找不出来 : double findMedian(int A[], int m, int B[], int n) { : if(!n) { : return (A[(m - 1)/ 2] + A[(m - 1)/ 2 + (m - 1) % 2]) / 2.0; : } : int aStart = -1, aEnd = (m + n - 1) / 2 - 1; : int bStart = -1, bEnd = 0;
| | | p*****2 发帖数: 21240 | 31
貌似玄铁的算法?
【在 B*******1 的大作中提到】 : My code, pass all the test. : double findKth(int a[], int m, int b[], int n, int k) : { : if (m > n) return findKth(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), pb = k - pa; : if (a[pa-1] < b[pb-1]) return findKth(a+pa, m-pa, b, n, k - pa); : return findKth(a, m, b+pb, n-pb, k-pb); : }
| B*******1 发帖数: 2454 | 32 是啊,学习大牛得。
【在 p*****2 的大作中提到】 : : 貌似玄铁的算法?
| C***U 发帖数: 2406 | 33 恩 用递归不错 果然好写好多
膜拜你
不过我最近想练习尽量不用递归。。。
【在 B*******1 的大作中提到】 : My code, pass all the test. : double findKth(int a[], int m, int b[], int n, int k) : { : if (m > n) return findKth(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), pb = k - pa; : if (a[pa-1] < b[pb-1]) return findKth(a+pa, m-pa, b, n, k - pa); : return findKth(a, m, b+pb, n-pb, k-pb); : }
| p*****2 发帖数: 21240 | 34
牛逼呀。膜拜一下。
【在 B*******1 的大作中提到】 : 是啊,学习大牛得。
| C***U 发帖数: 2406 | 35 我做leetcode前一半用递归。。。然后被我同学鄙视了
后一半我就不用递归了。。。嘎嘎
【在 p*****2 的大作中提到】 : : 牛逼呀。膜拜一下。
| p*****2 发帖数: 21240 | 36
不要死较真。看题。这题写成这样已经很牛逼了。我同样的算法用Java写,难写很多。
因为没有指针的灵活性。
【在 C***U 的大作中提到】 : 恩 用递归不错 果然好写好多 : 膜拜你 : 不过我最近想练习尽量不用递归。。。
| w****x 发帖数: 2483 | 37 对阿, median of 2 sorted array 就是kth element of two sorted array的变体,
后者简洁多了, 但是收敛速度不一样啊 | C***U 发帖数: 2406 | 38 好 明白了
哈哈哈
他写的code确实很牛 那么短!
【在 p*****2 的大作中提到】 : : 不要死较真。看题。这题写成这样已经很牛逼了。我同样的算法用Java写,难写很多。 : 因为没有指针的灵活性。
| D****3 发帖数: 611 | 39 这题leetcode有问题,我直接打public class Solution {
public double findMedianSortedArrays(int A[], int B[]) {
return 0;
}
}
他说我超时。。。他扯淡吧 | p*****2 发帖数: 21240 | 40
总是这样吗?有的时候人多会这样。
【在 D****3 的大作中提到】 : 这题leetcode有问题,我直接打public class Solution { : public double findMedianSortedArrays(int A[], int B[]) { : return 0; : } : } : 他说我超时。。。他扯淡吧
| | | C***U 发帖数: 2406 | 41 那应该是人品问题 哈哈哈
有时候他可能在维护什么的吧?
【在 D****3 的大作中提到】 : 这题leetcode有问题,我直接打public class Solution { : public double findMedianSortedArrays(int A[], int B[]) { : return 0; : } : } : 他说我超时。。。他扯淡吧
| e***s 发帖数: 799 | 42 LeetCode上这题的OJ很奇怪,O(n)居然能过Large case | Y********f 发帖数: 410 | 43 刚做了这道题,leetcode上为了不调用find kth elments两次写了一个比较复杂的。我
写了一个稍微简单点的,实际上也是基于find kth element.
double median2Array(int* arrA, int lenA, int* arrB, int lenB, int k, int
isEven)
{
if (lenA == 0)
return isEven ? (arrB[k-1] + arrB[k]) / 2.0 : arrB[k-1];
else if (lenB == 0)
return isEven ? (arrA[k-1] + arrA[k]) / 2.0 : arrA[k-1];
else if (k == 1)
{
vector vect(min(2, lenA) + min(2, lenB));
copy(arrA, arrA + min(2, lenA), vect.begin());
copy(arrB, arrB + min(2, lenB), vect.begin() + lenA);
sort(vect.begin(), vect.end());
return (isEven ? (vect[0] + vect[1]) / 2.0 : vect[0]);
}
int midA = (min(lenA, k) - 1) / 2;
int midB = (min(lenB, k) - 1) / 2;
if (arrA[midA] < arrB[midB])
return median2Array(arrA + midA + 1, lenA - midA - 1, arrB, lenB, k
- midA - 1, isEven);
else
return median2Array(arrA, lenA, arrB + midB + 1, lenB - midB - 1, k
- midB - 1, isEven);
}
double median2Array(int* arrA, int lenA, int* arrB, int lenB)
{
int isEven = ((lenA + lenB) % 2) ? 0 : 1;
return median2Array(arrA, lenA, arrB, lenB, (lenA + lenB + 1) / 2,
isEven);
}
【在 C***U 的大作中提到】 : 我把leetcode上好多例子拿到机器上测试了 都没出错 : 但是在leetcode上会time limit exceeded : 应该是有一个死循环 : 我找不出来 : double findMedian(int A[], int m, int B[], int n) { : if(!n) { : return (A[(m - 1)/ 2] + A[(m - 1)/ 2 + (m - 1) % 2]) / 2.0; : } : int aStart = -1, aEnd = (m + n - 1) / 2 - 1; : int bStart = -1, bEnd = 0;
| b***m 发帖数: 5987 | 44
代码我虽然看懂了,但是能不能说说思想?
【在 B*******1 的大作中提到】 : My code, pass all the test. : double findKth(int a[], int m, int b[], int n, int k) : { : if (m > n) return findKth(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), pb = k - pa; : if (a[pa-1] < b[pb-1]) return findKth(a+pa, m-pa, b, n, k - pa); : return findKth(a, m, b+pb, n-pb, k-pb); : }
| b***m 发帖数: 5987 | 45
其实思想我也大概明白了,就是不断把k减半进行收敛,最后达到两条退出条件之一(m
==0或者k==1),而决定后续递归的参数传入条件就是pa和pb点的选取以及比较。
【在 b***m 的大作中提到】 : : 代码我虽然看懂了,但是能不能说说思想?
| Y********f 发帖数: 410 | 46 刚做了这道题,leetcode上为了不调用find kth elments两次写了一个比较复杂的。我
写了一个稍微简单点的,实际上也是基于find kth element.
double median2Array(int* arrA, int lenA, int* arrB, int lenB, int k, int
isEven)
{
if (lenA == 0)
return isEven ? (arrB[k-1] + arrB[k]) / 2.0 : arrB[k-1];
else if (lenB == 0)
return isEven ? (arrA[k-1] + arrA[k]) / 2.0 : arrA[k-1];
else if (k == 1)
{
vector vect(min(2, lenA) + min(2, lenB));
copy(arrA, arrA + min(2, lenA), vect.begin());
copy(arrB, arrB + min(2, lenB), vect.begin() + lenA);
sort(vect.begin(), vect.end());
return (isEven ? (vect[0] + vect[1]) / 2.0 : vect[0]);
}
int midA = (min(lenA, k) - 1) / 2;
int midB = (min(lenB, k) - 1) / 2;
if (arrA[midA] < arrB[midB])
return median2Array(arrA + midA + 1, lenA - midA - 1, arrB, lenB, k
- midA - 1, isEven);
else
return median2Array(arrA, lenA, arrB + midB + 1, lenB - midB - 1, k
- midB - 1, isEven);
}
double median2Array(int* arrA, int lenA, int* arrB, int lenB)
{
int isEven = ((lenA + lenB) % 2) ? 0 : 1;
return median2Array(arrA, lenA, arrB, lenB, (lenA + lenB + 1) / 2,
isEven);
}
【在 C***U 的大作中提到】 : 我把leetcode上好多例子拿到机器上测试了 都没出错 : 但是在leetcode上会time limit exceeded : 应该是有一个死循环 : 我找不出来 : double findMedian(int A[], int m, int B[], int n) { : if(!n) { : return (A[(m - 1)/ 2] + A[(m - 1)/ 2 + (m - 1) % 2]) / 2.0; : } : int aStart = -1, aEnd = (m + n - 1) / 2 - 1; : int bStart = -1, bEnd = 0;
| b***m 发帖数: 5987 | 47
代码我虽然看懂了,但是能不能说说思想?
【在 B*******1 的大作中提到】 : My code, pass all the test. : double findKth(int a[], int m, int b[], int n, int k) : { : if (m > n) return findKth(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), pb = k - pa; : if (a[pa-1] < b[pb-1]) return findKth(a+pa, m-pa, b, n, k - pa); : return findKth(a, m, b+pb, n-pb, k-pb); : }
| b***m 发帖数: 5987 | 48
其实思想我也大概明白了,就是不断把k减半进行收敛,最后达到两条退出条件之一(m
==0或者k==1),而决定后续递归的参数传入条件就是pa和pb点的选取以及比较。
【在 b***m 的大作中提到】 : : 代码我虽然看懂了,但是能不能说说思想?
| w******j 发帖数: 185 | |
|