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.
|
|