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 的大作中提到】
: 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 的大作中提到】
: 写了个java版本，写吐了，虽然pass了。
: 大牛们，谁有简洁的java版本代码啊，贴上来给小的们开开眼吧。网上看了看，都不怎
: 么靠谱啊。
| t**********h
发帖数: 2273 | 5 这个是MIT那个算法改进版么？
别啊，还做题吧，java，做题两不误
【在 p*****3 的大作中提到】
:
: 以index为标准做的二分，two sorted array 找第k大的。
: （另外为了避免被版上大牛喷我发誓这个是N久以前的code,俺现在不做题一心一意学
: java）
| d****n
发帖数: 233 | 6
【在 t**********h 的大作中提到】
: 太牛了，不递归？我也要做到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 的大作中提到】
: 太牛了，不递归？我也要做到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 的大作中提到】
: 调用那个找第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 的大作中提到】
: 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 的大作中提到】
: 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.
|
|
