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 的大作中提到】
: 考虑最坏情况
|
|
