t**********h 发帖数: 2273 | 1 写了个java版本,写吐了,虽然pass了。
大牛们,谁有简洁的java版本代码啊,贴上来给小的们开开眼吧。网上看了看,都不怎
么靠谱啊。 | p*****3 发帖数: 488 | 2 static int searchKth(int[] a, int[] b, int k)
{
if (k <= 0)
return Math.min(a[0], b[0]);
if (k > a.length + b.length)
return Math.max(a[a.length-1], b[b.length-1]);
int l = 0;
int h = Math.min(a.length-1, k-1);
while (l <= h)
{
int x = (l + h)/2;
int a_x = a[x];
int a_x_1 = (x - 1 < 0 ? Integer.MIN_VALUE : a[x-1]);
int b_k_x = (k - x >= b.length ? Integer.MAX_VALUE : b[k-x]);
int b_k_x_1 = (k - x - 1 >= b.length ? Integer.MAX_VALUE : b[k-x
-1]);
if (a_x < b_k_x_1)
l = x + 1;
else if (a_x_1 > b_k_x)
h = x - 1;
else
return Math.max(a_x_1, b_k_x_1);
}
return -1;
} | t**********h 发帖数: 2273 | 3 太牛了,不递归?我也要做到800题,欧耶!
我贴下我的吧,哥是真做吐了,模仿的玄铁的算法。
public class Solution {
public double findMedianSortedArrays(int a[], int b[]) {
// Start typing your Java solution below
// DO NOT write main() function
int m = a.length;
int n = b.length;
int total = m + n;
if ((total & 0x1) == 1) {
return findKth(a, 0, m, b, 0, n, total / 2 + 1);
} else {
return (findKth(a, 0, m, b, 0, n, total / 2) + findKth(a, 0, m,
b, 0, n, total / 2 + 1)) / 2;
}
}
private double findKth(int[] a, int i, int m, int[] b, int j, int n, int
k) {
if (m > n) {
return findKth(b, j, n, a, i, m, k);
}
if (m == 0) {
return b[j + k - 1];
}
if (k == 1) {
return Math.min(a[i], b[j]);
}
int pa = Math.min(k / 2, m);
int pb = k - pa;
if (a[i + pa - 1] < b[j + pb - 1]) {
return findKth(a, i + pa, m - pa, b, j, n, k - pa);
} else if (a[i + pa - 1] > b[j + pb - 1]) {
return findKth(a, i, m, b, j + pb, n - pb, k - pb);
} else {
return a[i + pa - 1];
}
}
}
【在 p*****3 的大作中提到】![](/moin_static193/solenoid/img/up.png) : static int searchKth(int[] a, int[] b, int k) : { : if (k <= 0) : return Math.min(a[0], b[0]); : if (k > a.length + b.length) : return Math.max(a[a.length-1], b[b.length-1]); : : int l = 0; : int h = Math.min(a.length-1, k-1); : while (l <= h)
| p*****3 发帖数: 488 | 4
以index为标准做的二分,two sorted array 找第k大的。
(另外为了避免被版上大牛喷我发誓这个是N久以前的code,俺现在不做题一心一意学
java)
【在 t**********h 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 写了个java版本,写吐了,虽然pass了。 : 大牛们,谁有简洁的java版本代码啊,贴上来给小的们开开眼吧。网上看了看,都不怎 : 么靠谱啊。
| t**********h 发帖数: 2273 | 5 这个是MIT那个算法改进版么?
别啊,还做题吧,java,做题两不误
【在 p*****3 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 以index为标准做的二分,two sorted array 找第k大的。 : (另外为了避免被版上大牛喷我发誓这个是N久以前的code,俺现在不做题一心一意学 : java)
| d****n 发帖数: 233 | 6
【在 t**********h 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 太牛了,不递归?我也要做到800题,欧耶! : 我贴下我的吧,哥是真做吐了,模仿的玄铁的算法。 : public class Solution { : public double findMedianSortedArrays(int a[], int b[]) { : // Start typing your Java solution below : // DO NOT write main() function : int m = a.length; : int n = b.length; : int total = m + n; : if ((total & 0x1) == 1) {
| d****n 发帖数: 233 | 7 你这个其实很不错啊! 去掉无用的花括号,代码更容易读:
public class Solution {
public double findMedianSortedArrays(int a[], int b[]) {
int m = a.length;
int n = b.length;
int total = m + n;
if ((total & 0x1) == 1)
return findKth(a, 0, m, b, 0, n, total / 2 + 1);
else
return (findKth(a, 0, m, b, 0, n, total / 2) + findKth(a, 0, m,
b, 0, n, total / 2 + 1)) / 2;
}
private double findKth(int[] a, int i, int m, int[] b, int j, int n, int
k) {
if (m > n) return findKth(b, j, n, a, i, m, k);
if (m == 0) return b[j + k - 1];
if (k == 1) return Math.min(a[i], b[j]);
int pa = Math.min(k / 2, m);
int pb = k - pa;
if (a[i + pa - 1] < b[j + pb - 1]) return findKth(a, i + pa, m - pa,
b, j, pb, k - pa);
else return findKth(a, i, pa, b, j + pb, n - pb, k - pb);
}
}
【在 t**********h 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 太牛了,不递归?我也要做到800题,欧耶! : 我贴下我的吧,哥是真做吐了,模仿的玄铁的算法。 : public class Solution { : public double findMedianSortedArrays(int a[], int b[]) { : // Start typing your Java solution below : // DO NOT write main() function : int m = a.length; : int n = b.length; : int total = m + n; : if ((total & 0x1) == 1) {
| J****3 发帖数: 427 | | h******6 发帖数: 2697 | 9 调用那个找第k小的行不行?
类似于:
int total = a.length + b.length;
if(total % 2 == 1) {
return findKth(a, 0, a.length-1, b, 0, b.length-1, total/2+1);
}
else {
int t1 = findKth(a, 0, a.length-1, b, 0, b.length-1, total/2);
int t2 = findKth(a, 0, a.length-1, b, 0, b.length-1, total/2+1);
return (float)(t1 + t2) / 2;
} | m**********e 发帖数: 22 | 10 Does not work. If you have even number of total elements and the median
number is between the 2 elements in one array, the result is wrong. Check
the leetcode.
【在 h******6 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 调用那个找第k小的行不行? : 类似于: : int total = a.length + b.length; : if(total % 2 == 1) { : return findKth(a, 0, a.length-1, b, 0, b.length-1, total/2+1); : } : else { : int t1 = findKth(a, 0, a.length-1, b, 0, b.length-1, total/2); : int t2 = findKth(a, 0, a.length-1, b, 0, b.length-1, total/2+1); : return (float)(t1 + t2) / 2;
| B*****g 发帖数: 34098 | 11 这个为啥呢?
【在 m**********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Does not work. If you have even number of total elements and the median : number is between the 2 elements in one array, the result is wrong. Check : the leetcode.
| h******6 发帖数: 2697 | 12
下面这行不是对付这种情况的吗?难道我理解有误?
return (float)(t1 + t2) / 2;
【在 m**********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Does not work. If you have even number of total elements and the median : number is between the 2 elements in one array, the result is wrong. Check : the leetcode.
|
|