j********r
发帖数: 453 | 1 two unordered array, one long,n , one short, m, sort them into a large array
. Someone say that we can sort the short array, it's mlogm, and binary
search and insert the long, the total is nlogm. but i am not clear about the
insert part, how it can be nlogm.
If there is a better algorithm, please share.
Thank for helps. | q****x
发帖数: 7404 | 2 can't be better than O((n+m)log(n+m))
otherwise, you can always split one single unsorted array into long/short
pair.
array
the
【在 j********r 的大作中提到】
: two unordered array, one long,n , one short, m, sort them into a large array
: . Someone say that we can sort the short array, it's mlogm, and binary
: search and insert the long, the total is nlogm. but i am not clear about the
: insert part, how it can be nlogm.
: If there is a better algorithm, please share.
: Thank for helps.
| p*****2
发帖数: 21240 | 3
array
the
binary search也不是logm吧？注意m只是初始值，会越来越大。
【在 j********r 的大作中提到】
: two unordered array, one long,n , one short, m, sort them into a large array
: . Someone say that we can sort the short array, it's mlogm, and binary
: search and insert the long, the total is nlogm. but i am not clear about the
: insert part, how it can be nlogm.
: If there is a better algorithm, please share.
: Thank for helps.
|
|
