g**********y
发帖数: 14569 | 1 A/G都问的一道：Find kth smallest number in union of two sorted arrays
好象网上公认的最佳解是logM+logN。我写完code, 感觉log(min(M,N))就够了，如果错了，请指正。
思路是用的ihasleetcode的：i+j=k, 既然k是固定的，那我只需要找出i, 这个i我当然可以挑一个短的序列找。以下code是找针对数组a的指针i, 要是b是短的，稍改一下程序就行。
public int get(int[] a, int[] b, int k) {
int lower = Math.max(0, k-b.length-1);
int upper = Math.min(a.length-1, k-1);
int i = (lower + upper) / 2;
return get(a, b, k, lower, i, upper);
}
private int get(int[] a, int[] b, int k, int lower, int i, int upper) {
int j = k - i - 2;
if (j < 0) return Math.min(a[i], b[0]);
if (a[i] == b[j]) {
return a[i];
}
else if (a[i] < b[j]) {
if (i == upper) return b[j];
return get(a, b, k, i, (i+1+upper)/2, upper);
}
else { // a[i] > b[j]
if (i == lower) return a[i];
if (i == lower+1) return a[lower]>=b[j+1]? a[lower] : Math.min(a[i], b[j+1]);
return get(a, b, k, lower, (i-1+lower)/2, i);
}
} | i**********e
发帖数: 1145 | 2 很好的发现！赞！
你的想法是对的，在那里有读者曾在 comments 提出来。
There is an O(lg(min{m, n, k}) method. :-) FYI.
http://tanliboy.wordpress.com/2011/05/01/some-interesting-googl
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
错了，请指正。
然可以挑一个短的序列找。以下code是找针对数组a的指针i, 要是b是短的，稍改一下
程序就行。
【在 g**********y 的大作中提到】
: A/G都问的一道：Find kth smallest number in union of two sorted arrays
: 好象网上公认的最佳解是logM+logN。我写完code, 感觉log(min(M,N))就够了，如果错了，请指正。
: 思路是用的ihasleetcode的：i+j=k, 既然k是固定的，那我只需要找出i, 这个i我当然可以挑一个短的序列找。以下code是找针对数组a的指针i, 要是b是短的，稍改一下程序就行。
: public int get(int[] a, int[] b, int k) {
: int lower = Math.max(0, k-b.length-1);
: int upper = Math.min(a.length-1, k-1);
: int i = (lower + upper) / 2;
: return get(a, b, k, lower, i, upper);
: }
: private int get(int[] a, int[] b, int k, int lower, int i, int upper) {
| g**********y
发帖数: 14569 | 3 哦，我没读comments, 原来早有人发现了 :)
【在 i**********e 的大作中提到】
: 很好的发现！赞！
: 你的想法是对的，在那里有读者曾在 comments 提出来。
: There is an O(lg(min{m, n, k}) method. :-) FYI.
: http://tanliboy.wordpress.com/2011/05/01/some-interesting-googl
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
:
: 错了，请指正。
: 然可以挑一个短的序列找。以下code是找针对数组a的指针i, 要是b是短的，稍改一下
: 程序就行。
| s*****y
发帖数: 897 | 4 O(lg(min{m, n, k})
m = 1; K = 10 n = 20;
so it will be lg m ?
【在 i**********e 的大作中提到】
: 很好的发现！赞！
: 你的想法是对的，在那里有读者曾在 comments 提出来。
: There is an O(lg(min{m, n, k}) method. :-) FYI.
: http://tanliboy.wordpress.com/2011/05/01/some-interesting-googl
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
:
: 错了，请指正。
: 然可以挑一个短的序列找。以下code是找针对数组a的指针i, 要是b是短的，稍改一下
: 程序就行。
| g**********y
发帖数: 14569 | 5 对，答案只能是a[8], a[9], b[0]里的一个, 是常数次判断。
【在 s*****y 的大作中提到】
: O(lg(min{m, n, k})
: m = 1; K = 10 n = 20;
: so it will be lg m ?
| g******0
发帖数: 221 | 6 you are right about the running time.
Thanks for sharing the code.
错了，请指正。
然可以挑一个短的序列找。以下code是找针对数组a的指针i, 要是b是短的，稍改一下
程序就行。
【在 g**********y 的大作中提到】
: A/G都问的一道：Find kth smallest number in union of two sorted arrays
: 好象网上公认的最佳解是logM+logN。我写完code, 感觉log(min(M,N))就够了，如果错了，请指正。
: 思路是用的ihasleetcode的：i+j=k, 既然k是固定的，那我只需要找出i, 这个i我当然可以挑一个短的序列找。以下code是找针对数组a的指针i, 要是b是短的，稍改一下程序就行。
: public int get(int[] a, int[] b, int k) {
: int lower = Math.max(0, k-b.length-1);
: int upper = Math.min(a.length-1, k-1);
: int i = (lower + upper) / 2;
: return get(a, b, k, lower, i, upper);
: }
: private int get(int[] a, int[] b, int k, int lower, int i, int upper) {
| c******n
发帖数: 710 | | h*********3
发帖数: 111 | 8 多谢分享。
我觉得还是有2个问题：
1）一个corner case: a[]={1} b[]={2}, 找第一个最小的，你的j会变成-1,溢出了
2) (i == upper-1) 只判断 Math.min(a[upper], b[j]);
是不够的， 一个例子
a[] = {1,2,3} b[]={4,5,6}, 找第4个最小的，你的程序似乎是返回 5 .
写了一个c的，欢迎指正。
int m_FindKthFromTwoSortedArray(int arr1[],int len1,int arr2[],int len2,int k)
{
int m1,m2;
int l1=max(0,k-len2-1),r1=min(len1-1,k-1);
if ( k == 1 )
return min(arr1[0],arr2[0]);
m1 = l1 + (r1-l1)/2;
m2 = k-(m1+1)-1;
while ( arr1[m1] != arr2[m2] && m1 <= min(len1-1,k-1) && m1 >= max(0,k-len2-1))
{
if ( arr1[m1] < arr2[m2] )
{
if( m1 == len1-1 || arr2[m2] <= arr1[m1+1] )
return arr2[m2];
else
l1 = m1+1;
}
else
{
if( m2 == len2-1 || arr1[m1] <= arr2[m2+1] )
return arr1[m1];
else if ( m1 == 0 )
return max(arr1[0],arr2[k-1]);
else
r1 = m1-1;
}
m1 = l1 + (r1-l1)/2;
if (m1 == k-1)
return min(arr1[m1],arr2[0]);
m2 = k - (m1+1)-1;
}
return arr2[m2];
}
错了，请指正。
然可以挑一个短的序列找。以下code是找针对数组a的指针i, 要是b是短的，稍改一下
程序就行。
【在 g**********y 的大作中提到】
: A/G都问的一道：Find kth smallest number in union of two sorted arrays
: 好象网上公认的最佳解是logM+logN。我写完code, 感觉log(min(M,N))就够了，如果错了，请指正。
: 思路是用的ihasleetcode的：i+j=k, 既然k是固定的，那我只需要找出i, 这个i我当然可以挑一个短的序列找。以下code是找针对数组a的指针i, 要是b是短的，稍改一下程序就行。
: public int get(int[] a, int[] b, int k) {
: int lower = Math.max(0, k-b.length-1);
: int upper = Math.min(a.length-1, k-1);
: int i = (lower + upper) / 2;
: return get(a, b, k, lower, i, upper);
: }
: private int get(int[] a, int[] b, int k, int lower, int i, int upper) {
| g**********y
发帖数: 14569 | 9 谢谢指出错误，我写边界条件总容易出错，还是考虑不周密。
arr2[],int len2,int k)
【在 h*********3 的大作中提到】
: 多谢分享。
: 我觉得还是有2个问题：
: 1）一个corner case: a[]={1} b[]={2}, 找第一个最小的，你的j会变成-1,溢出了
: 2) (i == upper-1) 只判断 Math.min(a[upper], b[j]);
: 是不够的， 一个例子
: a[] = {1,2,3} b[]={4,5,6}, 找第4个最小的，你的程序似乎是返回 5 .
: 写了一个c的，欢迎指正。
: int m_FindKthFromTwoSortedArray(int arr1[],int len1,int arr2[],int len2,int k)
: {
: int m1,m2;
| s*****y
发帖数: 897 | 10 How about this one?
int Find_KthElement(int A[], int m, int B[], int n, int k)
{
if (k > m+n)
return 0;
if (m > n) {
return Find_KthElement(B,n,A,m,k);
}
int lo = 0;
int hi = min(m,k)-1;
while (lo < hi) {
int mid = lo + (hi-lo)/ 2;
int bIndex = k - mid - 2;
if (A[mid] < B[bIndex]) {
lo = mid +1;
} else {
hi = mid;
}
}
return max((A[lo] ? A[lo]:INT_MIN), (B[k-lo-2] ? B[k-lo-2]:INT_MIN));
}
arr2[],int len2,int k)
【在 h*********3 的大作中提到】
: 多谢分享。
: 我觉得还是有2个问题：
: 1）一个corner case: a[]={1} b[]={2}, 找第一个最小的，你的j会变成-1,溢出了
: 2) (i == upper-1) 只判断 Math.min(a[upper], b[j]);
: 是不够的， 一个例子
: a[] = {1,2,3} b[]={4,5,6}, 找第4个最小的，你的程序似乎是返回 5 .
: 写了一个c的，欢迎指正。
: int m_FindKthFromTwoSortedArray(int arr1[],int len1,int arr2[],int len2,int k)
: {
: int m1,m2;
| | | h*********3
发帖数: 111 | 11 你这个似乎有问题。
找最小的会溢出。
a[] = {1,2,3}
b[] = {4,5,6}
找第3小。
【在 s*****y 的大作中提到】
: How about this one?
: int Find_KthElement(int A[], int m, int B[], int n, int k)
: {
: if (k > m+n)
: return 0;
: if (m > n) {
: return Find_KthElement(B,n,A,m,k);
: }
: int lo = 0;
: int hi = min(m,k)-1;
| s*****y
发帖数: 897 | 12 Just try
K =1 return 1
K =3 return 3
【在 h*********3 的大作中提到】
: 你这个似乎有问题。
: 找最小的会溢出。
: a[] = {1,2,3}
: b[] = {4,5,6}
: 找第3小。
| h*********3
发帖数: 111 | 13 return max((A[lo] ? A[lo]:INT_MIN), (B[k-lo-2] ? B[k-lo-2]:INT_MIN));
k = 3 时候， k-lo-2 是-1, 溢出。
另外，a[]={1}, b[]={2}, 找最小也是溢出。
【在 s*****y 的大作中提到】
: Just try
: K =1 return 1
: K =3 return 3
| s*****y
发帖数: 897 | 14 Yes. You are right.
By luck I get the right answer even with this overflow.
【在 h*********3 的大作中提到】
: return max((A[lo] ? A[lo]:INT_MIN), (B[k-lo-2] ? B[k-lo-2]:INT_MIN));
: k = 3 时候， k-lo-2 是-1, 溢出。
: 另外，a[]={1}, b[]={2}, 找最小也是溢出。
| g**********y
发帖数: 14569 | 15 hehe, 我发现这个题就是很难写边界条件，太简单的code, 几乎注定要倒在边界条件上。
Interview时写，怕是注定要写错。完全不出错，肯定会被怀疑是在默写code :)
【在 s*****y 的大作中提到】
: How about this one?
: int Find_KthElement(int A[], int m, int B[], int n, int k)
: {
: if (k > m+n)
: return 0;
: if (m > n) {
: return Find_KthElement(B,n,A,m,k);
: }
: int lo = 0;
: int hi = min(m,k)-1;
| g**e
发帖数: 6127 | 16 这个题，面试的时候要写对全部边界条件，我觉得几乎是不可能... 除非硬背
上。
【在 g**********y 的大作中提到】
: hehe, 我发现这个题就是很难写边界条件，太简单的code, 几乎注定要倒在边界条件上。
: Interview时写，怕是注定要写错。完全不出错，肯定会被怀疑是在默写code :)
| p*****a
发帖数: 147 | 17 简单讲一下这个的idea吧
没怎么看懂
错了，请指正。
然可以挑一个短的序列找。以下code是找针对数组a的指针i, 要是b是短的，稍改一下
程序就行。
【在 g**********y 的大作中提到】
: A/G都问的一道：Find kth smallest number in union of two sorted arrays
: 好象网上公认的最佳解是logM+logN。我写完code, 感觉log(min(M,N))就够了，如果错了，请指正。
: 思路是用的ihasleetcode的：i+j=k, 既然k是固定的，那我只需要找出i, 这个i我当然可以挑一个短的序列找。以下code是找针对数组a的指针i, 要是b是短的，稍改一下程序就行。
: public int get(int[] a, int[] b, int k) {
: int lower = Math.max(0, k-b.length-1);
: int upper = Math.min(a.length-1, k-1);
: int i = (lower + upper) / 2;
: return get(a, b, k, lower, i, upper);
: }
: private int get(int[] a, int[] b, int k, int lower, int i, int upper) {
|
|
