g***j 发帖数: 1275 | 1 Given two sorted integer arrays A and B of size n and m respectively, find
the kth smallest element in the union of A and B in O(lg(n)+lg(m)) time....
我解法如下
找到 A 的 中间值 a, O(1), 然后在B里面找到比它小的数的个数, O(lg(m)), 两个数组中小于等于a的数字的和为t,
如果t=k, 则返回a;
如果t>k, 则丢掉所有比a大的数, 在剩下的数中间找kth smallest的
如果t
但是, 这个不是lg(n)+ lg(m)的吧? | s*****i 发帖数: 355 | 2 我来试一下
1. 先比较A[k/2]和B[k/2],设 A[k/2] <= B[k/2]。那么kth smallest一定在A[0..k]和
B[0..k/2]。
2. 然后比A[k/2]和B[k/4],如果A[k/2] <= B[k/4],同1,这时只用考虑A[0..k]和B[0
..k/4]
如果A[k/2]>B[k/4],那么kth smallest一定在A[k/2 .. k]和B[k/4 .. k/2]之间。因为
A[0..k/2]和B[0..k/4]一共只有3k/4个数
3. 按照1,2继续下去
最后应该就是O(log(n)+log(m))
数组中小于等于a的数字的和为t,
【在 g***j 的大作中提到】 : Given two sorted integer arrays A and B of size n and m respectively, find : the kth smallest element in the union of A and B in O(lg(n)+lg(m)) time.... : 我解法如下 : 找到 A 的 中间值 a, O(1), 然后在B里面找到比它小的数的个数, O(lg(m)), 两个数组中小于等于a的数字的和为t, : 如果t=k, 则返回a; : 如果t>k, 则丢掉所有比a大的数, 在剩下的数中间找kth smallest的 : 如果t: 但是, 这个不是lg(n)+ lg(m)的吧?
| t**r 发帖数: 512 | 3
]和
i think it should be inside a[k/2..k] b[0..k/2]
[0
因为
then i want to compare b[k/4] a[3k/4]
by this way,why the result is not log(k)
【在 s*****i 的大作中提到】 : 我来试一下 : 1. 先比较A[k/2]和B[k/2],设 A[k/2] <= B[k/2]。那么kth smallest一定在A[0..k]和 : B[0..k/2]。 : 2. 然后比A[k/2]和B[k/4],如果A[k/2] <= B[k/4],同1,这时只用考虑A[0..k]和B[0 : ..k/4] : 如果A[k/2]>B[k/4],那么kth smallest一定在A[k/2 .. k]和B[k/4 .. k/2]之间。因为 : A[0..k/2]和B[0..k/4]一共只有3k/4个数 : 3. 按照1,2继续下去 : 最后应该就是O(log(n)+log(m)) :
| s*****i 发帖数: 355 | 4 考虑最坏情况
【在 t**r 的大作中提到】 : : ]和 : i think it should be inside a[k/2..k] b[0..k/2] : [0 : 因为 : then i want to compare b[k/4] a[3k/4] : by this way,why the result is not log(k)
| h**k 发帖数: 3368 | 5
]和
这里可以再优化一下,如果A[k/2] <= B[k/2],kth smallest在A[k/2 ... k]和B[0..k
/2]。然后问题变成在A[k/2 ... k]和B[0..k/2]中找k/2 smallest。然后可以重复下去。
[0
因为
【在 s*****i 的大作中提到】 : 我来试一下 : 1. 先比较A[k/2]和B[k/2],设 A[k/2] <= B[k/2]。那么kth smallest一定在A[0..k]和 : B[0..k/2]。 : 2. 然后比A[k/2]和B[k/4],如果A[k/2] <= B[k/4],同1,这时只用考虑A[0..k]和B[0 : ..k/4] : 如果A[k/2]>B[k/4],那么kth smallest一定在A[k/2 .. k]和B[k/4 .. k/2]之间。因为 : A[0..k/2]和B[0..k/4]一共只有3k/4个数 : 3. 按照1,2继续下去 : 最后应该就是O(log(n)+log(m)) :
| l*****a 发帖数: 14598 | 6 一般说的复杂度都是平均情况吧?
你开始各取k/2
每次淘汰掉一半,
顶多logk次就剩一个元素比较了
我认为就可以有结果了。
【在 s*****i 的大作中提到】 : 考虑最坏情况
|
|