B*******1
发帖数: 2454 | 1 array1 长度M，array2长度N，要求O（logM+logN)
看了那本Algorithms for interviews，死活看不懂，Google老印写的书不但英文难懂
，而且错漏很多，真不懂这书都可以印刷出来，code都是错的，请高人指教一下。 |
l*****a
发帖数: 14598 | 2 比较array1[k/2] array2[k/2]
if = ,return
if array1[k/2]>array2[k/2] , array2[0..k/2]are definitely in the k smallest
then choose k/2 smallest
from array1[0..len1-1-k/2] array2[k/2+1..len2-1]
...
pay attention the boundary of the array.
【在 B*******1 的大作中提到】
: array1 长度M，array2长度N，要求O（logM+logN)
: 看了那本Algorithms for interviews，死活看不懂，Google老印写的书不但英文难懂
: ，而且错漏很多，真不懂这书都可以印刷出来，code都是错的，请高人指教一下。
|
s*****e
发帖数: 16824 | 3 直接merge两个array.
【在 B*******1 的大作中提到】
: array1 长度M，array2长度N，要求O（logM+logN)
: 看了那本Algorithms for interviews，死活看不懂，Google老印写的书不但英文难懂
: ，而且错漏很多，真不懂这书都可以印刷出来，code都是错的，请高人指教一下。
|
g*****a
发帖数: 1457 | |
g*****a
发帖数: 1457 | 5 那这样应该是lgK 和N,M没有关系吧
smallest
-1]
【在 l*****a 的大作中提到】
: 比较array1[k/2] array2[k/2]
: if = ,return
: if array1[k/2]>array2[k/2] , array2[0..k/2]are definitely in the k smallest
: then choose k/2 smallest
: from array1[0..len1-1-k/2] array2[k/2+1..len2-1]
: ...
: pay attention the boundary of the array.
|
f***g
发帖数: 214 | |
j*****u
发帖数: 1133 | 7 should be O(logK) since you started with 2k elements and drop half items eve
ry time
【在 B*******1 的大作中提到】
: array1 长度M，array2长度N，要求O（logM+logN)
: 看了那本Algorithms for interviews，死活看不懂，Google老印写的书不但英文难懂
: ，而且错漏很多，真不懂这书都可以印刷出来，code都是错的，请高人指教一下。
|
B*******1
发帖数: 2454 | 8 Thanks. I will check that book .
eve
【在 j*****u 的大作中提到】
: should be O(logK) since you started with 2k elements and drop half items eve
: ry time
|
