d********m
发帖数: 101 | 1 第一次做难度5，要跪了，耗费了一天时间还是晕。思路明白，但是看不懂代码
http://blog.csdn.net/yutianzuijin/article/details/11499917
网上找的代码
看不懂4跟11行，求助大神们！ | C********e
发帖数: 492 | 2 public double findMedianSortedArrays(int A[], int B[]) {
int len = A.length + B.length;
if (len % 2 == 1) {
return findKthSortedArrays(A, B, len / 2 + 1, 0, 0);
} else {
int left = findKthSortedArrays(A, B, len / 2, 0, 0);
int right = findKthSortedArrays(A, B, len / 2 + 1, 0, 0);
return (left + right) * 1.0 / 2;
}
}
private int findKthSortedArrays(int A[], int B[], int k, int startA, int
startB) {
if (startA >= A.length) {
return B[startB + k - 1 + (startA - A.length)];
}
if (startB >= B.length) {
return A[startA + k - 1 + (startB - B.length)];
}
if (k == 1) {
return Math.min(A[startA], B[startB]);
}
int p1 = k / 2;
int p2 = k - p1;
if (startA + p1 - 1 >= A.length) {
//return B[startB + k - 1 - (A.length - startA)];
p1 = A.length - startA;
p2 = k - p1;
}
if (startB + p2 - 1 >= B.length) {
//return A[startA + k - 1 - (B.length - startB)];
p2 = B.length - startB;
p1 = k - p2;
}
if (A[startA + p1 - 1] < B[startB + p2 - 1]) {
return findKthSortedArrays(A, B, k - p1, startA + p1, startB);
} else {
return findKthSortedArrays(A, B, k - p2, startA, startB + p2);
}
}
【在 d********m 的大作中提到】
: 第一次做难度5，要跪了，耗费了一天时间还是晕。思路明白，但是看不懂代码
: http://blog.csdn.net/yutianzuijin/article/details/11499917
: 网上找的代码
: 看不懂4跟11行，求助大神们！
| k*******a
发帖数: 433 | 3 你给的链接的时间复杂度是(m+n)log(m+n)，不符合题目要求啊 | r*******e
发帖数: 971 | 4 public class Solution {
public double findMedianSortedArrays(int A[], int B[]) {
if (A==null||B==null) return 0;
int len = A.length+B.length;
if ((len&1)>0)
return findKth(A,0,B,0,len/2+1);
else
return findKth(A,0,B,0,len/2)/2.0+findKth(A,0,B,0,len/2+1)/2.0;
}
private int findKth(int[] A,int a, int[] B,int b,int k){
if (a>=A.length) return B[b+k-1];
if (b>=B.length) return A[a+k-1];
if (k==1) return Math.min(A[a],B[b]);
int median_A = (a+k/2-1
int median_B = (b+k/2-1
if (median_A>median_B)
return findKth(A,a,B,b+k/2,k-k/2);
else
return findKth(A,a+k/2,B,b,k-k/2);
}
} | s**x
发帖数: 7506 | 5 这题最优解法应该是log(min(m,n,k)).
是少数难题之一。边界条件多，写对了真不容易。 | t*****3
发帖数: 112 | 6 第4行是为第11行服务的，第11行的目的是取两个数组的第k/2个元素来比较，问题是两
个数组长度不同时，且有可能短的数组会比k/2还小，这时候就必须要在k/2和较短的数
组的最后一个元素中取索引比较小的那个。举个简单例子：a = {1,3}和b = {2,4,6,8,
9}找第6小的数，那么k = 6, k/2 = 3, pa = 2, pb = 4, a[2 - 1] < b[4 - 1] --> b
[3]
【在 d********m 的大作中提到】
: 第一次做难度5，要跪了，耗费了一天时间还是晕。思路明白，但是看不懂代码
: http://blog.csdn.net/yutianzuijin/article/details/11499917
: 网上找的代码
: 看不懂4跟11行，求助大神们！
| d********m
发帖数: 101 | 7 明白了，多谢LS各位解释！
8,
b
【在 t*****3 的大作中提到】
: 第4行是为第11行服务的，第11行的目的是取两个数组的第k/2个元素来比较，问题是两
: 个数组长度不同时，且有可能短的数组会比k/2还小，这时候就必须要在k/2和较短的数
: 组的最后一个元素中取索引比较小的那个。举个简单例子：a = {1,3}和b = {2,4,6,8,
: 9}找第6小的数，那么k = 6, k/2 = 3, pa = 2, pb = 4, a[2 - 1] < b[4 - 1] --> b
: [3]
|
|
